|
Alternative Konzeption eines Kellerautomaten
als 6-Tupel: M = (Q, , , ,q0,#)
oder wie bisher als 7-Tupel, wobei die Menge der Endzustände leer ist: M = (Q,,,,q0,#,Ø)
Der Automat akzeptiert statt durch einen Endzustand durch einen leeren Keller, wenn die Eingabe vollständig abgearbeitet wurde.
Weitere Übergänge sind mit leerem Keller nicht mehr möglich.
|
Es muss sicher gestellt sein, dass der Automat MlK nicht irgendwann im Verlauf der Analyse "zufällig" einen leeren Keller hat,
mit dem er akzeptieren würde, obwohl MEZ keinen Endzustand erreicht hat.
Dieser Fall kann eintreten, wenn MEZ bei der Analyse eines Wortes x, das nicht zu L(MEZ) gehört,
eine Konfiguration mit leerem Keller erreicht. Auch MlK (der ja MEZ simuliert) würde einen leeren Keller haben und damit das Wort fälschlicherweise akzeptieren.
Um das zu verhindern, hat MlK ein zustätzliches Kellerstartsymbol, das nur dann gelöscht werden darf,
wenn MEZ einen Endzustand erreicht.
| MEZ | Mlk |
|---|
| Q | Q U {q'0,qe} | zusätzlicher Start- und besonderer Zustand zum Kellerleeren |
| | |
| U {#} | neues Kellerendzeichen |
|
- '(q'0,
 ,#) = {(q0,Z0#)}
- '(q,a,Z) = (q,a,Z) für alle q aus Q, a aus U {} und Z aus
- Für alle q aus F und Z aus U {#} gibt es (qe,) in '(q,,Z)
- Für alle Z aus U {#} gibt es (qe,) in '(qe,,Z)
| Initialisierung auf Startkonfig. von MEZ
Übernahme aller "normalen" Übergänge von MEZ
Erreicht MEZ einen Endzustand, so besteht die Möglichkeit für MlK in den Zustand zum Kellerleeren überzugehen.
Leeren des Kellers |
| Z0 | # | neues Kellerendsymbol, s. 'Kritischer Punkt' |
| q0 | q'0 | Start: (q'0,Wort,#)
Ziel: (qe,,) |
| F | Ø | Akzeptieren durch leeren Keller |
|
Simulation von MlK durch MEZ