There was a question on my exam asking to draw an automata with 2 states ("O" and "E") with the final state accepting ba^(n), for n>=1 and n had to be an odd number. I spent 45 minutes on it and I don't even think I got it right.
How would you draw it?
We may use Myhill-Nerode to prove that was has been requested is impossible. We can illustrate the equivalence classes w.r.t. the indistinguishability relation taken for this language.
Consider the empty string, e. It can be followed by any string in L to get a string in L. Therefore we have an equivalence class [e] corresponding to the initial state of the automaton. Note that this state is not accepting since e is not a string in the language.
Consider the string a. This can not be followed by any string to get a string in L, and so this is a different equivalence class [a]. Clearly a is not a string in the language and so this is not accepting. This cannot be the same state as corresponds to [e]; indeed, the state corresponding to [e] transitions to the state corresponding to [a] on the input a.
We now have two distinct non-accepting states that must appear in any minimal DFA recognizing L. Since L is non-empty (left as an exercise) there must be some other accepting state(s) in any minimal DFA. Therefore, there is non two-state DFA accepting L. QED
Continuing the analysis, the equivalence classes are [e], [a], [b] and [ba]. The transition table is:
q s q'
[e] a [a]
[e] b [b]
[a] a [a]
[a] b [a]
[b] a [ba]
[b] b [a]
[ba] a [b]
[ba] b [a]
The only accepting state is the one corresponding to [ba].