Proof for minimum number of states for a epsilon free NFA is $2^n$

Question

I have the following question which I could not proceed:

Let $$L=\{w \in \Sigma^* \mid \text{all symbols of the alphabet occur even times in } w\}. $$

Prove that any NFA accepting $L$ requires $2^n$ states, where $n$ is the size of the alphabet $\Sigma$.

I think I came up with a proof for a DFA using the Myhill-Nerode Theorem but I do not know how to generalize it to NFA's.

Edit:Relevant question is answered in https://stackoverflow.com/questions/9068873/how-do-we-know-that-an-nfa-has-a-minimum-amount-of-states .

Answer 1

The answer to the relevant question refers to a theorem of [1] that can be used to determine lower bounds on the number of states of a minimal NFA:

Theorem. Let $L \subseteq \Sigma^*$ be a regular language and suppose that there exist $n$ pairs of words $P = \{(u_i, v_i) \mid 1 \leqslant i \leqslant n \}$ such that:

1. $u_iv_i \in L$ for $1 \leqslant i \leqslant n$
2. $u_jv_i \notin L$ for $1 \leqslant i,j \leqslant n$ and $i \not= j$.

Then any NFA accepting $L$ has at least $n$ states.

Suppose that $\Sigma = \{a_1, \dots, a_n\}$. For each $i = (i_1, \dots, i_n) \in \{0, 1\}^n$, let $u_i = v_i = a_{i_1}^{i_1} a_{i_2}^{i_2} \dotsm a_{i_n}^{i_n}$. By construction, $u_i$ and $v_i$ satisfy the conditions (1) and (2). Since $|\{0, 1\}^n| = 2^n$, any NFA accepting $L$ has at least $2^n$ states.

[1] I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59 (2), pp. 75–77, (1996). DOI:10.1016/0020-0190(96)00095-6.