Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
I see. So if you can show M accepts other inputs not in L then it cannot exist? – James Dec 12 '12 at 1:23
@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$. – Brian M. Scott Dec 12 '12 at 1:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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