|
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.
|
Auch umgekehrt gilt: Immer wenn MlK ein Wort durch leeren Keller akzeptiert, wird auch ein ihn simulierender
MEZ in einen Endzustand übergehen und die Eingabe akzeptieren.
| MlK | MEZ |
|---|
| Q | Q U {q'0,qf} | zusätzlicher Start- und Endzustand |
| | |
| U {Z0} | neues Kellerendzeichen |
|
- '(q'0,
 ,Z0) = {(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 Q gibt es (qf,) in '(q,,Z0)
| Initialisierung auf Startkonfig. von MlK
Übernahme aller "normalen" Übergänge von MEZ
Ist Z0 bei vollständig verarbeiteten Wort wieder sichtbar, so hätte MlK einen leeren Keller. Somit kann MEZ in den Endzustand übergehen. |
| # | Z0 | neues Kellerendsymbol |
| q0 | q'0 | Start: (q'0,Wort,#)
Ziel: (qe,,) |
| Ø | qf | Akzeptieren im Endzustand |
|
1
2
Übersicht: Sprachklassen
