Theoretische Informatik - Deterministische Kellerautomaten (DKAs)

Nächste Seite: Akzeptanzbedingungen Aufwärts: Deterministische kontextfreie Sprachen Vorherige Seite: Eigenschaften Inhalt

Unterabschnitte

Deterministische Kellerautomaten (DKAs)

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.