deterministischer Kellerautomat (dPDA)

Definition

Ein deterministischer Kellerautomat (dPDA) ist ein PDA
$A=(Q,\Sigma ,\Gamma ,q_0,Z_0,△,F)$,
der die folgenden Eigenschaften erfüllt:

• Für alle $q\in Q,a\in \Sigma$ und $Z\in \Gamma$ gibt es genau einen Übergang der Form $(q,a,Z,\gamma ,q^{\prime })$ oder $(q,\epsilon ,Z,\gamma ,q^{\prime })$.
• Wenn ein Übergang das Kellerstartsymbol $Z_0$ entfert, so muss er es direckt wieder zurückscreiben;
  alle Übergänge, in denen $Z_0$ vorkommt, müssen also die Form $(q,a,Z_0,\gamma Z_0,q^{\prime })$ haben, mit $\gamma \in {\Gamma }^{\ast }$ beliebig.

siehe auch:
Deterministisch kontextfreie Sprachen