Notizen

Kellerautomat

tagstheoretische_informatik, formale_sprachtheorie
aliasesPushdown Automat, PDA

Ein Kellerautomat (Pushdown Automat, PDA) ist gegeben durch ein 6-Tupel , wobei:

  • ist eine endliche Zustandsmenge
  • ist ein endliches Bandalphabet
  • ist das endliche Kelleralphabet (Speicher)
  • ist die Transitionsfunktion
    • Signatur:
    • Menge aller endlichen Teilmengen der Menge X
  • ist der Startzustand
  • : Ursprüngliches Kellersymbol (Blank-Symbol)

Siehe auch

Chomsky-Hierachie

Akzeptanz eines Kellerautomaten

Es gibt keine akzeptierten Endzustände, stattdessen akzeptiert der Automat ein Wort wenn:

  • Das Wort wurde komplett gelesen
  • Der Keller (Speicher) ist leer

Notation der Übergangsfunktion

Die Übergangsfunktion wird notiert durch

  • : Aktueller Zustand
  • : Gelesenes Zeichen aus dem Wort
  • : Zeichen was aus dem Stack geholt wurde
  • : Neuer Zustand
  • : Neue(s) Zeichen was in den Stack geschrieben werden soll

Notation: Konfigurationsübergänge

Beispiel: Kompletter PDA für eine Sprache

PDA-Übergangsfunktionen:

Misplaced &q_0, a, \# &\rightarrow q_0, A\# \\ q_0, a, A &\rightarrow q_0, AA \\ q_0, b, A &\rightarrow q_1, \epsilon \\ q_1, b, A &\rightarrow q_1, \epsilon \\ q_1, \epsilon, \# &\rightarrow q_2, \epsilon \end{align}$$

Backlinks