FSK-7VL-04-06-2024

Themen

• 7a: Äquivalenz von kontextfreien Sprachen und von Kellerautomaten
• 7b: Deterministische Kellerautomaten
• 7c: Turingmaschienen

VL-07a Äquivalenz von kontextfreien Sprachen und von Kellerautomaten

Wiederholung (SimpleClub Video empfehlenswert für grobes Verständnis)

• DEA un NAS haben keinen Speicher also brauchen PDAs (Pushdown Automata / Kellerautomaten)
• Keller funktionieren nach LIFO
• ist ein 6-Tupel $$M=\{Z,\Sigma ,\Gamma ,\delta ,z_0,\#\}$$
• Keller ist unendlich groß und am ende steht immer ein #
• Wort liegt in der Sprache, wenn der Keller leer ist und kein Zeichen mehr übrig ist

Aufbau der Verarbeitungsschritte im PDA

$$q_0,a,A\to q_1,B$$ $$\underset{\text{Zustand}}{\underbrace{q_o}},\underset{\text{gelesenes Zeichen}}{\underbrace{a}},\stackrel{\text{Zeichen aus Stack}}{\overbrace{A}}\to \underset{\text{neuer Zustand}}{\underbrace{q_1}},\stackrel{\text{neues Zeichen im Stack}}{\overbrace{B}}$$

Kontextfreie Sprachen werden von PDAs akzeptiert

Satz

Für jede kontextfreie Sprache $L$ gibt es einen PDA $M$ mit $L(M)=L$.

Beweis Skript 7a S.3-4

Beispiel für die Konstruktion eines PDA aus einer Grammatik Skript 7a S.5

Grammatik zu PDA (Kontextfrei)

Die akzeptierte Sprache von PDAs ist kontextfrei S.7-9

Äquivalenz von kontextfreien Sprachen und von Kellerautomaten S.14

VL07-b DPDAs

DPDA brauchen keinen Müllzustand

DPDAs effizientes Parsing

VL-07c Turingmaschinen

f

---