# Turing machine that accepts L = {#a != #b}

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?

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

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.