Reference no: EM131708982

Question: Determine what the Turing machine in Example does when presented with the inputs aba and aaabbbb.

Example: For Σ = {a,b}, design a Turing machine that accepts

L = {a_nb_n : n ≥ 1}

Intuitively, we solve the problem in the following fashion. Starting at the leftmost a, we check it off by replacing it with some symbol, say x. We then let the read-write head travel right to find the leftmost b, which in turn is checked off by replacing it with another symbol, say y. After that, we go left again to the leftmost a, replace it with an x, then move to the leftmost band replace it with y, and so on. Traveling back and forth this way, we match each a with a corresponding b. If after some time no a's or b's remain, then the string must be in L.