Consider the language L = {w | the string w starts with an a}, where the string made up of two alphabets {a, b}. Prove that no DFA with two states recognises L.

Above is the question. I know it has to be more than two states. If the first letter is b, then the first/initial state will go to fail state and will never reach the accepting state. So that means, one accepting state, one fail state and the initial state. 3 States

But I don't know how to write or prove it in a formal way.

  • 1
    $\begingroup$ The Myhill-Nerode theorem gives a construction of the DFA with a minimum number of states recognizing an alphabet. $\endgroup$
    – TomKern
    Commented May 30, 2021 at 14:47

1 Answer 1


Given a language $L$, the Myhill-Nerode equivalence relation $R_L$ on finite words is such that:

$x \; R_L \; y$ if $\forall z: (x^{\frown}z \in L \iff y^{\frown}z \in L)$.

(${}^{\frown}$ is concatenation)

Each equivalence class of this equivalence relation corresponds to a state of the minimum deterministic automaton recognizing $L$. In some sense the equivalence relation is keeping track of exactly what information a deterministic automaton needs to keep track of.

If two starts of words $x$ and $y$ put you in a situation where no matter what sequence of letters $z$ you read next the automaton doesn't care whether you started with $x$ or $y$, there's no reason to distinguished between having read $x$ or having read $y$.

Of course if two starts of words $x$ and $y$ put you in a situation where there is some sequence of letters $z$ that will eventually distinguish the two starts, you need separate states to keep track of having read $x$ or having read $y$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .