Right Move
Definition: Let
c, c’ be
two configurations of M. Then, M makes a right move from c to c’ according to
r, written as c |–R c’ [r] or,
simply, c |–R c’ if c = xpay, r: pa |– qbR Î R and
a
x
y
p

Configuration
(1) c’ = xbqy, y ¹ e or
(2) c’ = xbqD, y = e
a
x
y
p
b
x
y
q
New
Configuration
b
x
y
q
a
x
p
Configuration
a
x
p
or
D
…
D
b
x
q
New
Configuration
b
x
q
D
D
…
D
10/45