Keller-Automaten
Id: keller.tex,v 1.2 2003/12/08 14:26:47 joe Exp
im Prinzip wie endlicher Automat, aber als Arbeitsspeicher nicht nur Zustand, sondern auch Keller (Band).
data Konfiguration x y z = Konfiguration { eingabe :: [ x ] , zustand :: z , keller :: [ y ] }
Ein Arbeitsschritt ist abhängig vom obersten Kellersymbol und Zustand und besteht aus:
Keller-Automaten (II)
data NPDA x y z = NPDA { eingabealphabet :: Set x , kelleralphabet :: Set y , zustandsmenge :: Set z , startzustand :: z , startsymbol :: y , akzeptiert :: Modus z , tafel :: FiniteMap (Maybe x, z, y) (Set (z, [y])) }
Übergangsrelation , falls
Sprachen von Keller-Automaten
Die durch leeren Keller akzeptierte Sprache:
Die durch Endzustandsmenge akzeptierte Sprache:
(Beachte in beiden Fällen: -Übergänge sind noch möglich.)
Keller-Automaten-Sprachen und CFG
Satz: Für alle Sprachen gilt: CFG mit Kellerautomat mit .
Beweis ( )
Keller-Automaten als Parser
Determinismus!
Übung (10./12. 12. 03) autotool/Kellerautomaten
Id: bastelkeller.tex,v 1.1 2003/12/10 10:13:39 joe Exp
Aufgaben Acceptor-NPDA(det)-{OGleich,Gleich,Pali,Dyck}
bitte heute diese Adresse benutzen: http://theo1.informatik.uni-leipzig.de/~joe/cgi-bin/Face.cgimatrikel: 318, wort: guest
Beispiel:
NPDA { eingabealphabet = mkSet "ab" , kelleralphabet = mkSet "XA" , zustandsmenge = mkSet [ 0, 1, 2] , startzustand = 0 , startsymbol = 'X' , akzeptiert = Leerer_Keller -- ODER: , akzeptiert = Zustand ( mkSet [ 2 ] ) , tafel = listToFM [ ( ( Just 'a', 0 , 'X'), mkSet [ ( 0, "AX")]) , ( ( Just 'a', 0 , 'A'), mkSet [ ( 0, "AA")]) , ( ( Just 'b', 0 , 'A'), mkSet [ ( 2, "") ]) , ( ( Just 'b', 2 , 'A'), mkSet [ ( 2, "") ]) ] }