# Regular language not accepted by DFA having at most three states

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

-
yes z can be ^ empty, but I think you have typo in your quote. xy^i ∈ L should be xy^i z ∈ L – Grijesh Chauhan Mar 29 '14 at 5:44
Thanks, corrected. – Yuval Filmus Mar 29 '14 at 12:26

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)

-
Nice answer: it explains a lot without giving away the solution to what looks like a homework exercise. Welcome to Computer Science! – David Richerby Feb 20 '14 at 9:26

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.

-
The language we obtain using your construction is $\emptyset$, which is trivially recognizable using one state. (Try to write a proof that the resulting language cannot be recognized by a DFA using 3 or fewer states and see what happens.) – D.W. Feb 22 '14 at 1:37
hmmm ok. correction/retouching/take2: need to construct the union out of all DFAs but altering/"flipping" each DFAs word symbol accepted in the $n$th position. how about that einstein? & thx for the hint/correction – vzn Feb 22 '14 at 3:55
On the other hand, there are finitely many DFAs with $n$ or fewer states, so they accept finitely many languages (if we fix an alphabet). Since there are infinitely many regular languages, some must require $n+1$ states. – Yuval Filmus Mar 29 '14 at 16:03
@Yuval right. think this idea can work but maybe dont have the details exactly right, details are tricky, would guess it might be somewhere in the literature but havent seen it – vzn Mar 29 '14 at 16:10