Turing Machine: Example 2/2
a
s
b
D
…
D
Note: M deletes a symbol before the first occurrence of D:
b/b, R
p
q
s
f
a/D, S
a/a, R
a/a, R
b/b, R
b/D, S
D/D, L
D/D, S
Illustration:
TM M:
…
a
p
b
D
D
a
p
b
D
…
D
a
q
b
D
…
D
a
f
D
D
…
D
7/45