Number of states required for deterministic finite automata

528 Views Asked by At

Lemma in text: Let $c$ be a constant and $L = \{1^c\}$ (the singleton language containing the string of $c$ many 1's). Then no DFA with < $c$ states can accept $L$.

The given proof assumes $\exists$ a DFA, $M$, with < $c$ states that accepts $L$ and ends with a contradiction showing how $M$ must accept infinitely more inputs than $\{1^c\}$.

I was wondering how the conclusion that $M$ accepts more inputs than those in $L$ implies $M$ cannot exist. Can a DFA not accept/recognize more than one language by design?

1

There are 1 best solutions below

2
On BEST ANSWER

By definition the language $L(M)$ recognized by a DFA $M$ is the set of words that $M$ accepts. Since this set is well-defined, $M$ recognizes exactly one language. The proof shows that if $M$ has fewer than $c$ states and accepts the word $1^c$, then it also accepts other words, so $L(M)\supsetneqq\{1^c\}$.