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

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 .

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.

• Thank you for the answer! Nov 29, 2018 at 6:20