0
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Help yourself by proving your answer. $\endgroup$ Aug 26, 2017 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, 2017 at 8:03
  • $\begingroup$ It's not hard to see which two states are equal. $\endgroup$
    – rus9384
    Aug 26, 2017 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, 2017 at 18:05

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
6
  • $\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$ Aug 26, 2017 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, 2017 at 11:27
  • $\begingroup$ Can you please show the diagram or tell me the software so that I can show mine . $\endgroup$ Aug 26, 2017 at 11:29
  • $\begingroup$ No, you have to find by yourself. $\endgroup$
    – J.-E. Pin
    Aug 26, 2017 at 11:30
  • 1
    $\begingroup$ Your automaton is not minimal. $\endgroup$
    – J.-E. Pin
    Aug 26, 2017 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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