Pravý přechod
Definice: Nechť c, c’ jsou dvě konfigurace TS M. Potom M může
provést pravý přechod
z c do c’ použitím r, zapsáno c |–R c’ [r] nebo
zjednodušeně c |–S c’ pokud: c = xpay, r: pa |– qbR Î R a současně:
a
x
y
p

Konfigurace
(1) c’ = xbqy, y ¹ e nebo
(2) c’ = xbqD, y = e
a
x
y
p
b
x
y
q
Nová konfigurace
b
x
y
q
nebo
a
x
p
Konfigurace
a
x
p
D
…
D
b
x
q
Nová konfigurace
b
x
q
D
D
…
D
10/45