Nichtdeterministischer Kellerautomat

Einfache Sprache

Ein nichtdeterministischer Kellerautomat ist ein NEA der einen Kellerspeicher hat um sich Symbole zu merken.

Def. Nichtdeterministischer Kellerautomat

Ein nichtdeterministischer Kellerautomat (NDKA) ist eine Struktur $(Q,A,\Gamma,\delta,q_0,Z_0,F)$ mit:

• $Q$ ist die endliche Menge von Zuständen oder Zustandsmenge.
• $A$ ist die endliche Menge an Eingabesymbole oder Eingabealphabet.
• $\Gamma$ ist die endliche Menge an Kellersymbolen oder Kelleralphabet.
• $\delta:Q\times A_\epsilon\times\Gamma\rightarrow \mathcal{P}(Q)\times\Gamma$ -> Transitionsfunktion mit $A_\epsilon=A\cup\{\epsilon\}$ die eine Zustand, ein Eingabesymbol und ein Kellersymbol auf eine Menge von Tupel bestehend aus Zustand und Kellersymbol abbildet.
• $I\in Q$ -> Startzustände
• $Z_0\in\Gamma^*$ -> Startinhalt des Kellerspeichers.
• $F\subseteq Q$ -> Menge der Endzustände

• Konfiguration eines Kellerautomaten
• Folgekonfiguration eines Kellerautomaten
• Erweiterte Folgekonfiguration eines Kellerautomaten
  • Satz ungelesene Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht