Construct a Turing machine that generates the set ai bi i

Construct a Turing machine that generates the set {a^i b^i | i >= 0}

Solution

Since the length of any string w B is odd, w must have a symbol exactly in the middle position; i.e., |w| = 2n + 1 for some n 0, and the (n + 1)th symbol in w is the middle one. If a string w of length 2n + 1 satisfies w = wR, the first n symbols must match (in reverse order) the last n symbols, and the middle symbol doesn’t have to match anything. Thus, in the above PDA, the transition from q2 to itself reads the first n symbols and pushes these on the stack. The transition from q2 to q3 nondeterministically identifies the middle symbol of w, which doesn’t need to match any symbol, so the stack is unaltered. The transition from q3 to itself then reads the last n symbols of w, popping the stack at each step to make sure the symbols after the middle match (in reverse order) the symbols before the middle.