machine. Still, it is possible, and the concept is easy to understand, as the next
examples illustrate.
Example 9.7
For Σ = {a,b}, design a Turing machine that accepts
L= {a n b 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.
Working out the details, we arrive at a complete solution for which Q=
{q 0 ,q 1 ,q 2 ,q 3 ,q 4 },F= {q 4 }, Σ= {a,b},Γ={a,b, x, y, }. The transitions can be
broken into several parts. The set
δ (q 0 , a)=(q 1 , x,R),
δ (q 1 , a)=(q 1 , a,R),
δ (q 1 , y)=(q 1 , y,R),
δ (q 1 , b)=(q 2 , y,R),
replaces the leftmost a with an x, then causes the read-write head to travel right
to the first b, replacing it with a y. When the y is written, the machine enters a
state q 2 , indicating that an a has been successfully paired with a b.
The next set of transitions reverses the direction until an x is encountered,
repositions the read-write head over the leftmost a, and returns control to the
initial state.
δ (q 2 ,y)=(q 2 ,y,L),
examples illustrate.
Example 9.7
For Σ = {a,b}, design a Turing machine that accepts
L= {a n b 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.
Working out the details, we arrive at a complete solution for which Q=
{q 0 ,q 1 ,q 2 ,q 3 ,q 4 },F= {q 4 }, Σ= {a,b},Γ={a,b, x, y, }. The transitions can be
broken into several parts. The set
δ (q 0 , a)=(q 1 , x,R),
δ (q 1 , a)=(q 1 , a,R),
δ (q 1 , y)=(q 1 , y,R),
δ (q 1 , b)=(q 2 , y,R),
replaces the leftmost a with an x, then causes the read-write head to travel right
to the first b, replacing it with a y. When the y is written, the machine enters a
state q 2 , indicating that an a has been successfully paired with a b.
The next set of transitions reverses the direction until an x is encountered,
repositions the read-write head over the leftmost a, and returns control to the
initial state.
δ (q 2 ,y)=(q 2 ,y,L),