0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ No, no DFA with 4 states can accept $L=\{111\}$. $\endgroup$ – Steven Mar 4 at 20:15
  • $\begingroup$ Hint: Consider how to not accept words which are not in $L$. $\endgroup$ – Watercrystal Mar 4 at 20:23
  • $\begingroup$ How about q0 -> q1 -> q2 -> q3 and each transition occurs on the symbol 1? @Steven $\endgroup$ – rjohnson1000 Mar 4 at 20:30
  • $\begingroup$ 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.) $\endgroup$ – Steven Mar 4 at 20:42
  • 1
    $\begingroup$ Depends on how you define it, but in the usual (vanilla) definition requires that. $\endgroup$ – Watercrystal Mar 4 at 20:54
3
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Steven Mar 4 at 22:05
  • $\begingroup$ Using this theorem is nice, but overkill ... $\endgroup$ – reinierpost Mar 5 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.