# Prove that no DFA with two states recognises L.

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.

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

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