# Prove that there is no $DFA$ with less than $2^n$ states that accepts $L_n =\{w\in\Sigma^*_n\ |\ \exists\sigma\in\Sigma_n\ :\ ⋕_\sigma(w)=0\}$

I've faced this question in my homework and I couldn't provide elegant proof for it.

We're given $$\Sigma_n=\{1,\dots,n\}$$ and a language: $$L_n =\{w\in\Sigma^*_n\ |\ \exists\sigma\in\Sigma_n\ :\ ⋕_\sigma(w)=0\}$$ That is a language that consists of letters from $$\Sigma_n$$ but doesn't contain all the letters.

Question: We're asked to prove that there is no $$DFA$$ with less than $$2^n$$ states that accepts $$L_n$$.

Note: It's given that there is $$NFA$$ with $$(n+1)$$ states that accepts $$L_n$$.

• Have you learned "Myhill–Nerode theorem"? Have you read the proof for it? Mar 18, 2022 at 20:26
• Yea I did, I tried actually to use it but it was hard at some point. Mar 18, 2022 at 20:28
• Suppose $n=1$. List all different equivalence classes, where each class can be represented by a (shortest) string in it. Do the same for $n=2$. You may see the pattern. Mar 18, 2022 at 20:33
• @JohnL. Thanks John, I appreciate your tip, I will try to follow it and understand how the proof works. Mar 18, 2022 at 20:41

You can use the Myhill-Nerode theorem for the given task. You must provide at least $$2^n$$ prefixes $$p_i\in \Sigma_n^*$$ belonging to the different equivalence classes, e.g. s.t. for every two prefixes $$p_i$$, $$p_j$$ there exists a suffix $$s_{i,j}$$ s.t. $$p_i s_{i,j}\in L_n$$ and $$p_j s_{i,j}\notin L_n$$ or vice versa.
Given your task, such prefixes correspond to all possible subsets of the alphabet $$\Sigma_n$$. There are $$2^n$$ such subsets, and the strings containing all the letters from the chosen subset $$S_i$$ and no other letters definitely satisfy the Myhill-Nerode equivalence class criterion. Given two words $$p_i$$, $$p_j$$ corresponding to the subsets $$S_i$$ and $$S_j$$, s.t. $$S_i\not\subseteq S_j$$, the suffix $$p_k$$ corresponding to the set $$S_k=\Sigma_n\setminus S_i$$ discerns $$p_i$$ and $$p_j$$, since $$p_i p_k\not\in L_n$$ and $$p_j p_k\in L_n$$.
• I reviewed your answer and I have a question. What about the case where we're given two words $p_i ,\ p_j$ corresponding to the subsets $S_i$ and $S_j$, s.t. $S_i \subseteq S_j$? Mar 21, 2022 at 16:36
• If the subsets $S_i$ and $S_j$ are not equal, then $S_i\subseteq S_j$ simply implies $S_j\not\subseteq S_i$, and the symmetric reasoning holds. Mar 21, 2022 at 18:24