# 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

## 1 Answer

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.

• I have also added one for dead state ! And n cant be odd in this case because a and b both are equal – Pradeep Kumar Aug 26 '17 at 11:26
• I also added one for dead state... Without it, the number of states would be 9. – J.-E. Pin Aug 26 '17 at 11:27
• Can you please show the diagram or tell me the software so that I can show mine . – Pradeep Kumar Aug 26 '17 at 11:29
• No, you have to find by yourself. – J.-E. Pin Aug 26 '17 at 11:30
• Your automaton is not minimal. – J.-E. Pin Aug 26 '17 at 12:03