Sprachen von Keller-Automaten

Übergangsrelation (w, z, k)$\to_{A}^{}$(w', z', u'k'), falls

• w = xw' für x $\in$ $\Sigma$ und k = yk' und (z', u') $\in$ T(x, z, y)
• oder w = w' und k = yk' und (z', u') $\in$ T($\epsilon$, z, y)

akzeptierte Sprachen:

• die durch leeren Keller akzeptierte Sprache: L_K(A) = {w | $\exists$z : (w, z₀,[y₀])$\to^{*}_{}$($\epsilon$, z,$\epsilon$)}
• die durch Endzustandsmenge F akzeptierte Sprache: L_F(A) = {w | $\exists$z $\in$ F, k $\in$ Y^* : (w, z₀,[y₀])$\to^{*}_{}$($\epsilon$, z, k)}

(Beachte in beiden Fällen: $\epsilon$-Übergänge sind noch möglich.)