# Minimal DFA: Number of states

I am trying to solve a problem with regards to a DFA. What is the minimal number of states for the following language:

$$L:=\{x\in\{a,b\}^n\ \ | \ \ |x|_a=|x|_b\}$$

where $|x|_a$ denotes the amount of $a$'s in the word $x$. I have done some calculations and got $3\cdot2^{(n/2)}-1$. Is this the correct number of states?

Here is the DFA for $n=4$:

• Help yourself by proving your answer. – Yuval Filmus Aug 26 '17 at 8:02
• How did you arrive at this number and why do you doubt your result? "Verify my answer" questions are not a good fit for this site. – adrianN Aug 26 '17 at 8:03
• It's not hard to see which two states are equal. – rus9384 Aug 26 '17 at 14:18
• Try enumerate each state by number of already read a's and b's. This must help. – rus9384 Aug 26 '17 at 18:05

Hint. Your answer is plain wrong. First, it trivially does not work if $n$ is odd. But it is also wrong if $n$ is even (except for $n = 2$). Just compute the minimal automaton of $\{aabb,abab,abba,baab,baba,bbaa\}$ to be convinced. Your formula gives $3\cdot 2^2 - 1 = 11$ states but the minimal automaton only has $10$ states.