Deterministischer Kellerautomat

Einfache Sprache

Normalerweise ist mit “Kellerautomat” ein NDKA gemeint.

Def. Deterministischer Kellerautomat

Ein NDKA ist deterministisch, also ein DKA, genau dann, wenn

1. $\forall q\in Q,a\in A_\varepsilon,X\in\Gamma: |\delta(q,a,X)|\leq 1$
2. $\forall q\in Q,X\in\Gamma:(\exists a\in A: \delta(q,a,X)\not=\emptyset)\implies\delta(q,\varepsilon,X)=\emptyset$