Suche Home Einstellungen Anmelden Hilfe  

3.3.2 Äquivalenz von Akzeptieren durch Endzustand und Akzeptieren durch leeren Keller

Simulation eines durch leeren Keller akzeptierenden KA (MlK) durch einen durch Endzustand akzeptierenden KA (MEZ)

Alternative Konzeption eines Kellerautomaten
als 6-Tupel: M = (Q,Sigma,Gamma,delta,q0,#)
oder wie bisher als 7-Tupel, wobei die Menge der Endzustände leer ist: M = (Q,Sigma,Gamma,delta,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.

Der neue Kellerautomat umschließt den alten Kellerautomaten und hat einige zusätzliche Übergänge

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.

MlKMEZ
QQ U {q'0,qf}zusätzlicher Start- und Endzustand
SigmaSigma 
GammaGamma U {Z0}neues Kellerendzeichen
delta
  • delta'(q'0,epsilon,Z0) = {(q0,#Z0)}
  • delta'(q,a,Z) = delta(q,a,Z) für alle q aus Q, a aus Sigma U {epsilon} und Z aus Gamma
  • Für alle q aus Q gibt es (qf,epsilon) in delta'(q,epsilon,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.
#Z0neues Kellerendsymbol
q0q'0Start: (q'0,Wort,#)
Ziel: (qe,epsilon,epsilon)
ØqfAkzeptieren im Endzustand

Simulation von MEZ durch Mlk 1   2 Übersicht: Sprachklassen

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: