Cur rent
state
Sym bol
read
Sym bol
writ ten
Direc tion
Next
state
Find the left end of the input
q 0
a
a
L
q 0
q 0
b
b
L
q 0
q 0
#
#
R
q 1
If leftmost sym bol is “a”, erase it, if “b” fail
q 1
a
#
R
q 2
q 1
b
#
R
q 4
Find the right end of the input
q 2
a
a
R
q 2
q 2
b
b
R
q 2
q 2
#
#
L
q 3
Erase the “b” at the left end of the input
q 3
b
#
L
q 0
The basic operation of this machine is a loop:
q 0 : move all the way to the left
q 1 : erase on ‘a’
q 2 : move all the way to the right
q 3 : Erase a ‘b’
Repeat
If the string is not of the form {
:
},
a b n
n n
≥ 0 it will finally either
(a) See an ‘a’ in nonfinal state q 3 , and halt, or
(b) see a ‘b’ in final state q 1 , move to nonfinal state q 4 , and halt.
4.1.7 Turing Machines as Trans ducers
To use a Turing machine as a transducer, treat the entire nonblank portion of
the initial tape as input, and treat the entire nonblank portion of the tape when
the machine halts as output.
A Turing machine defines a function y = f (x) for strings x y
,
*
∈ Σ if
q x q y
f
0 |–
*
where q f is the final state.
Turing Machines
189