Develop Turing Machine to count number of As and Bs in a String

Question

The given Language is L = {a^n b^n where n>= 0} I have to develop a turing machine for it but i dont get the logic. will it go like this if an a is not followed by a b you go to halt reject state, but how we check if the count of a and b are equal? will be very grateful for any response

Answer 1

A Turing Machine decides a language if it enters the halt-accept state when the input tape initially contains a string in the language, and enters the halt-reject state otherwise.

So, to decide your language L, you need to define states and transitions so that when the tape contains a string a^n b^n the TM ends up in halt-accept, and such that it ends up in halt-reject otherwise.

We can assume a single-tape TM and that you don't need the input tape restored to its original state after processing has finished (that is, we can do whatever we want to the tape and don't need to clean up or move the tape head anywhere in particular). What we need is a strategy for processing the tape so that we can reliably know when the string is or isn't in the language. In your case, we need a's followed by b's, with the same number of a's and b's. If you had to do this task in real life, how might you approach it?

You could first count the a's and then count the b's, and then see if the numbers are equal; however, this doesn't really simplify matters for us, since telling whether two numbers are equal is actually a somewhat harder problem than telling if two strings have the same length (the language ww | w in {a, b}* is context-sensitive, whereas a^n b^n is context-free).

Another approach is the "one for me, one for you" approach used by pirates when dividing treasure and mathematicians when establishing bijections among sets: to show that two sets have the same number of elements, you simply pair them off such that all elements are in exactly one pair. This doesn't yield the same problem that counting did, in that we don't have the same subproblem to solve: whereas the other problem yielded a harder subproblem, this one yields a subproblem of exactly the same difficulty as the original. Indeed, it's a smaller instance of the exact same problem! By erasing one a and then erasing a corresponding b, we can reduce a problem of size n to one of size n - 2. By repeating this process, we will eventually erase the whole tape and accept, or run out of symbols to pair with, and reject.

This is our design. For implementation, we will require an initial state. From the initial state, we can assume we are looking at the first non-blank tape cell, if any. If the tape cell is blank, the input is empty and we must accept since a^0 b^0 is in the language with n = 0. If the tape cell has b, we may halt-reject since we were expecting to see an a, if anything, first. If the tape cell has a, then we need to look for a corresponding b to erase.

Now, which b should we erase? Currently, we know where the input ends since we have a blank immediately after the last input symbol. If we use blanks to erase b's before that, we will have no good way of knowing whether we might have more input to the right of any currently blank cell. You could overcome this by introducing a new tape symbol E for erased cells; then, when erasing, write E instead of blank to indicate erasure. Then, it really doesn't matter which b you erase. If you prefer not to use a new tape symbol, however, you can instead erase the b immediately before the blank at the end of the input (rejecting if an a is found there instead) and achieve the same thing.

In any event, after erasing a corresponding b, we can return to the beginning of the tape (the blank cell first reached after moving left) and repeat the process over and over again until we accept or reject.

Here is a sample implementation:

Q    T    Q'    T'    D
--   -    --    --    -

// accept on empty tape
q0   B    hA    B     S

// erase an a or reject if no a
q0   a    q1    B     R
q0   b    hR    b     S

// scan to end of input
q1   B    q2    B     L
q1   a    q1    a     R
q1   b    q1    b     R

// erase last b or reject if none
q2   B    qR    B     S
q2   a    qR    a     S
q2   b    q3    B     S

// scan to beginning of input, then repeat
q3   B    q0    B     R
q3   a    q3    a     L
q3   b    q3    b     L