next up previous
Nächste Seite: Top-Down/Bottom-Up (Wiederholung) Aufwärts: Syntakt. Analyse (4. 12.) Vorherige Seite: Operator-Präzedenz-Parser

Keller-Automaten

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 $ y$ und Zustand $ z$ 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 $ (w, z, k) \to_A (w', z', u' k')$, falls

Sprachen von Keller-Automaten

Die durch leeren Keller akzeptierte Sprache: $ L_K(A)
= \{ w \mid \exists z: (w, z_0, [y_0]) \to^* (\epsilon, z, \epsilon) \} $

Die durch Endzustandsmenge $ F$ akzeptierte Sprache: $ L_F(A)
= \{ w \mid \exists z \in F, k \in Y^*:
(w, z_0, [y_0]) \to^* (\epsilon, z, k) \} $

(Beachte in beiden Fällen: $\epsilon$-Übergänge sind noch möglich.)

Keller-Automaten-Sprachen und CFG

Satz: Für alle Sprachen $ L$ gilt: $ \exists $ CFG $ G$ mit $ L(G)=L$ $ \iff$ $ \exists $ Kellerautomat $A$ mit $ L(A)=L$.

Beweis ( $\Rightarrow$)

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, "") ])
             ]
     }


next up previous
Nächste Seite: Top-Down/Bottom-Up (Wiederholung) Aufwärts: Syntakt. Analyse (4. 12.) Vorherige Seite: Operator-Präzedenz-Parser
Johannes Waldmann 2004-01-28