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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityAssume we have a language L={111}. Prove no DFA with four states can accept L.
Can’t a DFA with 4 states accept L?
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
(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).