0
$\begingroup$

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 Answers 1

3

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\}$.

  • 0
    @James: I’d not put it quite that way. What you’ve shown is that any DFA that accepts $1^c$ also accepts other words, so there is no DFA that accepts $1^c$ and **only** $1^c$.2012-12-12