Přechod u ZA
Definice: Nechť xApay a xwqy jsou dvě konfigurace ZA M, kde x, w Î G*, A Î G, p, q Î Q, a Î S È {e} a y Î S*. Nechť r = Apa ® wq Î R je pravidlo. Potom  M může provést přechod z xApay do xwqy za použití r, zapsáno xApay |– xwqy [r] nebo zjednodušeně  xApay |– xwqy.
Pozn.: pokud a = e, není ze vstupu přečten žádný symbol
Pravidlo: Apa ® wq
 Myšlenka: Jeden výpočetní krok ZA
Konfigurace:
a
p
A
y
x
Nová konfigurace:
q
…
w
…
y
x
26/50