Direkt zum Inhalt

Lexikon der Mathematik: deterministischer Kellerautomat

(engl. deterministic pushdown automaton, DPDA), ein Keller-automat mit deterministischer Überführungsrelation. Das heißt, daß der Nachfolgezustand und die Kelleroperation aus aktuellem Zustand, Eingabezeichen und oberstem Kellersymbol eindeutig bestimmt sind.

Der Automat ist bestimmt durch das Tupel \begin{eqnarray}[Q,\Sigma, \Gamma, \delta, {q}_{0},F].\end{eqnarray}

Dabei ist Q die Zustandsmenge, Σ das Eingabe-alphabet, 2 das Alphabet der Kellerzeichen. δ ist die partielle Überführungsrelation. Sie ordnet jedem Tripel [q, x, k] (aktueller Zustand, Eingabezeichen, oberstes Kellersymbol) aus Q × Σ ∪ {ϵ} × Γ ein Paar [z, w] (neuer Zustand, Folge neu zu kellernder Zeichen) aus Q × Γ zu.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos