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