Přechod
Definice: Nechť pax a qx jsou dvě konfigurace KA M, kde p, q Î Q, a Î S È {e} a x Î S*. Nechť r = pa ® q Î R je pravidlo. Potom M může provést přechod z pax do qx za použití r, zapsáno pax |– qx [r] nebo zjednodušeně pax |– qx
Pozn.: pokud a = e, není ze vstupní pásky přečten symbol
Pravidlo: pa ® q
 Myšlenka: Jeden výpočetní krok KA
13/29
Konfigurace:
a
p
x
Nová konfigurace:
q
…
x