Turingův stroj: Příklad 1/2
M = (Q, S, G, R, s, F)
• S = {a, b};
kde:
• G = {a, b, D};
s
p
q
• Q = {s, p, q, f};
f
• F = {f}
b/b, R
pb ® pbR,
sa ® paR,
a/a, R
sb ® pbR,
b/b, R
qa ® fDS,
a/D, S
qb ® fDS}
b/D, S
pD ® qDL,
D/D, L
pa ® paR,
a/a, R
• R = {sD ® fDS,
D/D, S
6/45