Suche Home Einstellungen Anmelden Hilfe  

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

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

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

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.

MEZMlk
QQ U {q'0,qe}zusätzlicher Start- und besonderer Zustand zum Kellerleeren
SigmaSigma 
GammaGamma U {#}neues Kellerendzeichen
delta
  • delta'(q'0,epsilon,#) = {(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 F und Z aus Gamma U {#} gibt es (qe,epsilon) in delta'(q,epsilon,Z)
  • Für alle Z aus Gamma U {#} gibt es (qe,epsilon) in delta'(qe,epsilon,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'
q0q'0Start: (q'0,Wort,#)
Ziel: (qe,epsilon,epsilon)
FØAkzeptieren durch leeren Keller

1  2 Simulation von MlK durch MEZ

Benutzer: Gast • Besitzer: senn • Zuletzt gešndert am: