# Prove no DFA with four states can accept L={111}

Assume we have a language L={111}. Prove no DFA with four states can accept L.

Can’t a DFA with 4 states accept L?

• No, no DFA with 4 states can accept $L=\{111\}$. – Steven Mar 4 at 20:15
• Hint: Consider how to not accept words which are not in $L$. – Watercrystal Mar 4 at 20:23
• How about q0 -> q1 -> q2 -> q3 and each transition occurs on the symbol 1? @Steven – rjohnson1000 Mar 4 at 20:30
• That DFA has 5 states, not $4$. (There is one implicit state to handle all the transitions you have not specified. The transition function of a DFA must be a total function.) – Steven Mar 4 at 20:42
• Depends on how you define it, but in the usual (vanilla) definition requires that. – Watercrystal Mar 4 at 20:54

This depends on your favorite definition for DFAs. If your definition allows the transition function to be undefined on some state-symbol pairs $$(q, a)$$ then your DFA in your comment does the trick. Otherwise, you would need a fifth state (a sink) that is not accepting and catches all missing transitions.

To show that there is no DFA with less than five states accepting $$L = \{111\}$$, we can check the Myhill-Nerode equivalence classes of $$L$$ which are

• $$[\varepsilon]_L = \{\varepsilon\}$$,
• $$[1]_L = \{1\}$$,
• $$[11]_L = \{11\}$$,
• $$[111]_L = \{111\}$$,
• $$[0]_L = \{w \in \{0, 1\}^\ast \mid w \notin \{\varepsilon, 1, 11, 111\}\}$$.

(To show that these are indeed the five classes is left as exercise.)

The equivalence classes have a 1:1 correspondence to the unique minimal DFA of the latter definition (with transitions for all state-symbol pairs).

• Notice that for the Myhill-Nerode theorem to work, the definition of DFA must require that transition function is a total function. Otherwise, as OP has shown, the theorem is not true since the number of states of a DFA that recognizes a language can be smaller than the number of equivalence classes. – Steven Mar 4 at 22:05
• Using this theorem is nice, but overkill ... – reinierpost Mar 5 at 13:37