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
Rule: pa ® qbR
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
Rule: pa ® qbR
a
x
p
Configuration
a
x
p
or
D
…
D
b
x
q
New Configuration
b
x
q
D
D
…
D
10/45