| Aus 4 mach 7 |
Konstruktion eines KA auf der Grundlage einer Grammatik
| Grammatik G | Kellerautomat M |
|---|
| | {q} | |
| T | T | |
| N | T N | |
| P |  |
- Für jede Regel LS > RS in P gibt es einen
 -Übergang (q, RS) in (q, , LS)
(Nur der Kellerinhalt wird betrachtet, nicht die Eingabe - Hypothesenbildung)
- Für jedes Terminalsymbol a in T gibt es einen Übergang (q, a, a)={(q, a)}
(Ableich von aktuellem Eingabesymbol und oberstem Kellersymbol - Verifikation)
|
| | q | Der Automat startet mit der Konfiguration (q, w, S) und akzeptiert mit (q, , ) |
| S | S | Das unterste Kellersymbol ist S |
| | Ø | M akzeptiert durch leeren Keller |
|
Vom KA zur Grammatik