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 community
Describe a regular language that cannot be accepted by any DFA that has only three states.
I'm not really sure where to start on this and was wondering if someone could give me some tips or advice. I understand that the pumping lemma can be used to prove a language is not regular, but in this case, it should be a regular language. If anyone has any thoughts it would be appreciated.
The pumping lemma can be stated to take into account the number of states in the DFA. Every language $L$ accepted by a DFA with $p$ states satisfies the following pumping lemma:
Each word $w$ of length at least $p$ can be broken up as $w=xyz$, where $|xy| \leq p$ and $|y| \geq 1$, such that $xy^iz \in L$ for all $i \geq 0$.
You can use this characterization to prove that the language $\{0^p\}$ requires $p+1$ states.
Another method is to use the Myhill--Nerode theorem. Two words $x,y$ are inequivalent (with respect to some language $L$) if for some word $z$, either $xz \in L$ and $yz \notin L$ or the other way around. The Myhill--Nerode theorem states that if there are $p$ pairwise inequivalent words, then every DFA for $L$ has at least $p$ states. For the example $L = \{0^p\}$, you can find $p+1$ pairwise inequivalent words, namely $\epsilon,0,\ldots,0^p$.
z can be ^ empty, but I think you have typo in your quote. xy^i ∈ L should be xy^i z ∈ L
$\endgroup$
Mar 29, 2014 at 5:44
Yuval's answer is great. A simpler formulation of what he's described is that finite automata cannot count arbitrarily high, and the amount they can count to is bounded by the number states in the automata. More precisely, for an automata to count to $p$, it needs $p+1$ states (one state would be $0$).
This is, in essence, the entire idea behind the pumping lemma: if a string is really long, the finite automata must "forget" how high its counted and start all over again, allowing you to repeat a section over and over without it caring.
Therefore, any regular language that requires counting to 3 to validate a word in it, cannot be described by a finite automata of size 3.
Can you think of such a language? (Your professor may also expect you to prove this counting argument, though in my curriculum this understanding of the pumping lemma was taken for granted)
There is an algorithm to minimize DFAs. Just pick a language which has a minimal DFA of 4 (or more) states. Anything that has a minimal length of 3 symbols will do, i.e., the language of the regular expression $a^3 a^*$, or (even simpler) $a^3$. To see why, take a peek at the proof of the pumping lemma for regular languages.
another idea, diagonalization! enumerate all 3-or-fewer-state DFAs, take the union of all of them, and then take the complement. this is a DFA by regular language operations closure. this could be constructed via an algorithm, but the question only asks for a description.
