Suche Home Einstellungen Anmelden Hilfe  

4.3.2 Vom KA zur Grammatik

Vom 7-Tupel zum 4-Tupel

 

 

 

 

 

Vom Übergang zur Regel
Zusammenhang zwischen Übergang und Regel

Konstruktion einer Grammatik auf der Grundlage eines KA

Kellerautomat MGrammatik G
Q{S}Vereinigung{[pZq] | für alle p und q aus Q und jedes Z aus Gamma} 
SigmaSigma=T 
Gamma Gamma wird zusammen mit den Zuständen in N kodiert
deltaP
  • Startregeln: S -> [q0Zp] für jedes p aus Q
  • Für jeden Übergang (p,B1B2...Bk) Element(q,a,A):
    [qApk] -> a [pB1p1][p1B2p2]...[pk-1Bkpk] (für jedes beliebige p1 ... pk aus Q und ein k >=0)
q0S 
#  
Ø  
Alle Nichtterminale, nach dem Muster [Zustand1 Kellersymbol Zustand2] zusammengesetzten Symbole, sind folgendermaßen zu verstehen:
  • Zustand1 - Zustand vor Verarbeitung von Kellersymbol
  • Zustand2 - Zustand nach Verarbeitung von Kellersymbol, also wenn das Symbol aus dem Keller entfernt wurde
Da der Zustand des Automaten nach der Verarbeitung eines Symbols nicht bekannt ist, werden Regeln für jeden Zustand zu P hinzugefügt.
Wieso gilt nun: [pAq] =>m w gdw. (q,w,Z) |-m (p,epsilon,epsilon)?

Beweis durch Induktion:

  1. m=0: Für m=0 gilt weder [pAq] =>0 w noch (q,w,Z) |-0 (p,epsilon,epsilon). Somit ist die Äquivalenz erfüllt (in einer Implikation ist die Folgerung aus etwas Falschem immer wahr)
  2. Induktionschritt: [pAq] =>m+1 w existiert gdw. (q,w,Z) |-m+1 (p,epsilon,epsilon).
    1. "=>"
    2. "<="

Von der Grammatik zum KA 1   2 Kontextfreie Grammatiken und Kellerautomaten

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