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?
6
-
$\begingroup$ No, no DFA with 4 states can accept $L=\{111\}$. $\endgroup$– StevenMar 4, 2021 at 20:15
-
$\begingroup$ Hint: Consider how to not accept words which are not in $L$. $\endgroup$– WatercrystalMar 4, 2021 at 20:23
-
$\begingroup$ How about q0 -> q1 -> q2 -> q3 and each transition occurs on the symbol 1? @Steven $\endgroup$– rjohnson1000Mar 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$– StevenMar 4, 2021 at 20:42
-
1$\begingroup$ Depends on how you define it, but in the usual (vanilla) definition requires that. $\endgroup$– WatercrystalMar 4, 2021 at 20:54
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
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).
-
$\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$– StevenMar 4, 2021 at 22:05
-
$\begingroup$ Using this theorem is nice, but overkill ... $\endgroup$ Mar 5, 2021 at 13:37