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$: DFA n=4

  • 2
    $\begingroup$ Help yourself by proving your answer. $\endgroup$ – Yuval Filmus Aug 26 '17 at 8:02
  • 1
    $\begingroup$ 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. $\endgroup$ – adrianN Aug 26 '17 at 8:03
  • $\begingroup$ It's not hard to see which two states are equal. $\endgroup$ – rus9384 Aug 26 '17 at 14:18
  • $\begingroup$ Try enumerate each state by number of already read a's and b's. This must help. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.