Kellerautomaten (PDA)

Definition

Ein Kellerautomat (PDA) ist ein Tupel
$A=(Q,\Sigma ,\Gamma ,q_s,Z_s,△,F)$, wobei

• $Q$ eine endliche Menge von Zuständen ist,
• $\Sigma$ das Eingabealphabet ist,
• $\Gamma$ das Kelleralphabet ist,
• $q_s\in Q$ der Anfangszustand ist,
• $Z_s\in \Gamma$ das Kellerstartsymbol ist,
• $△\subseteq Q\times (\Sigma \cup \{\epsilon \}\times \Gamma \times {\Gamma }^{\ast }\times Q)$ eine endliche Übergangsrelation ist und
• $F\subseteq Q$ eine Menge von akzeptierenden Zuständen ist.

Die Übergangsrelation

Beispiel Automat für {$a^n{b}^n|n\ge 1$}

Zu lesenden Zeichen / Der Kopf vom Stack / Was auf den Stack geschrieben wird

Akzeptanz per leerem Keller

Kellerautomat Akzeptanz per Zustand zu per leeren Keller
Kellerautomat Akzeptanz per leeren Keller zu per Zustand

Satz

Sprache von Grammatik ⇐> Sprache von Kellerautomat

siehe auch:

• deterministischer Kellerautomat (dPDA)