Trying to figure out how to make a deterministic single-tape Turing machine for the language of words comprising as many $a$'s as $b$'s.

I am very confused, because I can't figure out how I would keep track of how many $a$'s and $b$'s there would be. The method for finding $a^nb^n$ goes right and back left to do this but this language would include things like $abaaaababab$.

How can I keep track of number of $a$'s and $b$'s?

  • $\begingroup$ Sorry if I was unclear, it means the number of a's cannot equal the number of b's $\endgroup$
    – John
    Mar 4, 2018 at 15:49
  • 1
    $\begingroup$ When clarifying the question, you should not use a comment, but edit your question $\endgroup$
    – chi
    Mar 4, 2018 at 21:07

1 Answer 1


You dont need to keep track of them. At each iteration you have three possibilities. Either you first see an A, or a B or a nothing. If nothing accept. If an A first, replace it with some special character and search for a B. If you see one replace that one as well with some special character go back to beginning but if you dont just reject. Do the same for B first. After you cross our 2 characters loop back to beginning. It is actually very similar to $a^nb^n$.

The TM design should be straightforward actually. Similar to $a^nb^n$ but considers $b$ first option as well at each iteration.

  • $\begingroup$ I don't think this approach will work because you'd be introducing blank characters in your input string. When you're trying to go back to the beginning and you get to a blank, you won't be able to tell whether this is a blank you wrote to the tape (and there are more characters to the left of that blank) or whether you're actually at the beginning. Instead of replacing with a blank, you could cross off with some other character like an X. $\endgroup$ Mar 5, 2018 at 20:31
  • $\begingroup$ Yeah you are right it's a careless mistake but the algorithm TM design remains same. Thanks. $\endgroup$
    – sunnytheit
    Mar 5, 2018 at 20:36

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.