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, 2021 at 20:15
  • $\begingroup$ Hint: Consider how to not accept words which are not in $L$. $\endgroup$ Mar 4, 2021 at 20:23
  • $\begingroup$ How about q0 -> q1 -> q2 -> q3 and each transition occurs on the symbol 1? @Steven $\endgroup$ Mar 4, 2021 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, 2021 at 20:42
  • 1
    $\begingroup$ Depends on how you define it, but in the usual (vanilla) definition requires that. $\endgroup$ Mar 4, 2021 at 20:54

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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