Ψ Die Informatikseite

Menü
Unterabschnitte

Deterministische Kellerautomaten (DKAs)

Definition

Ein DKA ist ein NKA

\begin{displaymath}K=(Q,\Sigma,\Gamma,\delta,q_{0},\char93 ,F)\end{displaymath}

mit folgenden Einschränkungen
  • $\vert\delta(q,a,A)\vert\leq 1$:
    Von jedem Zustand darf höchstens ein Übergang mit derselben Inschrift für dasselbe oberste Kellersymbol stattfinden (dasselbe wie bei deterministischen Automaten)
  • $\vert\delta(q,\epsilon,A)\vert\leq 1$:
    Es darf von jedem Zustand höchstens ein $\epsilon$-Move für dasselbe oberste Kellersymbol ausgehen.
  • $\vert\delta(q,a,A)\cup \delta(q,\epsilon,A)\vert\leq 1$:
    Wenn ein $\epsilon$-Übergang von einem Zustand ausgeht, so darf von diesem kein weiterer Übergang mit demselben obersten Kellersymbol ausgehen.

Eingliederung in die Chomskyhierarchie