Kellerautomaten in autotool

Benutzung

Der Automat aus dem Skript, Seite 56 oben, sieht so aus:

import NPDA

data Z = Z0 | Z1 
     deriving (Eq, Ord, Show)

-- der Automat soll { w ~w  |  w  in  {0, 1}* }
-- durch leeren Keller akzeptieren

student :: NPDA Integer Char Z
student = NPDA { eingabealphabet = mkSet [ 0, 1 ]
	       , kelleralphabet  = mkSet "abc"
	       , zustandsmenge	 = mkSet [ Z0, Z1 ]
	       , tafel = t
	       , startzustand	 = Z0
	       , startsymbol	 = 'a'
	       , endzustandsmenge = emptySet
	       }

-- die Tabelle direkt aus dem Skript abgeschrieben

t = listToFM [ -- Spalte 1 (Z0, x = 0)
	       ( ( Just 0 , Z0, 'a'), mkSet [ ( Z0, "ba") ] )
	     , ( ( Just 0 , Z0, 'b'), mkSet [ ( Z0, "bb"), ( Z1, "") ] )
	     , ( ( Just 0 , Z0, 'c'), mkSet [ ( Z0, "bc") ] )
	     
	     -- Spalte 2 (Z0, x = 1)
	     , ( ( Just 1 , Z0, 'a'), mkSet [ ( Z0, "ca") ] )
	     , ( ( Just 1 , Z0, 'b'), mkSet [ ( Z0, "cb") ] )
	     , ( ( Just 1 , Z0, 'c'), mkSet [ ( Z0, "cc"), (Z1, "") ] )
	     
	     -- Spalte 3 (Z0, x = epsilon)
	     , ( ( Nothing, Z0, 'a'), mkSet [ ( Z1, "") ] )

	     -- Spalten 4 bis 6 (Z1)
	     , ( ( Just 0 , Z1, 'b'), mkSet [ ( Z1, "" ) ] )
	     , ( ( Just 1 , Z1, 'c'), mkSet [ ( Z1, "" ) ] )
	     , ( ( Nothing, Z1, 'a'), mkSet [ ( Z1, "" ) ] )
	     ]

Ansatz für Aufgabe IV.3

Probieren Sie aus, ob das folgende eine Lösung ist:

import NPDA

data Z = Z0 | Z1 
     deriving (Eq, Ord, Show)

-- der Automat soll { u a v b  |  |u| = |v| }
-- durch leeren Keller akzeptieren

student :: NPDA Char Char Z
student = NPDA { eingabealphabet = mkSet "ab"
	       , kelleralphabet  = mkSet "c"
	       , zustandsmenge	 = mkSet [ Z0, Z1 ]
	       , tafel = t
	       , startzustand	 = Z0
	       , startsymbol	 = 'c'
	       , endzustandsmenge = emptySet
	       }

t = listToFM   [ ((Just 'a',Z0,'c'), mkSet [(Z0,"cc"),(Z1,"c")])
	       , ((Just 'a',Z1,'c'), mkSet [(Z1,"")])
	       , ((Just 'b',Z0,'c'), mkSet [(Z0,"cc")])
	       , ((Just 'b',Z1,'c'), mkSet [(Z1,"")])
	       ]

Wenn nein, ergänzen und/oder korrigieren Sie entsprechend.

Tricks

(Zum Lösen der Übungsaufgaben nicht notwendig.)

Mit List comprehensions läßt sich das Beispiel (Seite 56, siehe oben) kürzer schreiben:

t' = plusFM_C unionSet speichern prüfen

speichern = listToFM 
    [ ( ( Just x, Z0, y ), mkSet [ ( Z0, [h, y] ) ] )
    | (x, h) <- [ (0, 'b'), (1, 'c') ]
    , y <- "abc"
    ]

prüfen	  = listToFM 
    [ ( ( x, z, y ), mkSet [ ( Z1, "" ) ] )
    | (x, y) <- [ ( Just 0, 'b'), ( Just 1, 'c'), ( Nothing, 'a') ]
    , z <- [ Z0, Z1 ]
    ]

Implementierung

(Auch diesen Abschnitt brauchen Sie weder zu lesen noch zu verstehen. Er ist aber hilfreich, wenn Sie das autotool zu hause installieren und selbst dran basteln.)

Wir implementieren einen Kellerautomaten direkt, wie er im Buche steht (Definition siehe Skript Seite 54). Der Datentyp ist

data NPDA x y z = 
     NPDA { eingabealphabet  :: Set x 
	  , kelleralphabet   :: Set y 
	  , zustandsmenge    :: Set z 
	  , tafel	     :: FiniteMap (Maybe x, z, y) (Set (z, [y]))
	  , startzustand     :: z
	  , startsymbol	     :: y
	  , endzustandsmenge :: Set z
	  }

Dabei ist [y] der Typ der Listen mit Elementen aus y, Set a ist der Typ der Mengen mit Elementen aus y, und FiniteMap a b sind endliche Abbildungen (stellen Sie sich Hashtabellen oder Suchbäume vor) mit Schlüsseln aus a und Werten aus b. Ein Element vom Typ Maybe x enthält entweder ein Just x oder Nothing.

Die Automatentabelle ist also tatsächlich eine Abbildung

(X + epsilon) x Z x Y  -> Pow ( Z x Y* )

Lesen Sie bei Bedarf hier Erläuterungen zum verwendeten Mailprozessor.

Es kann sein, daß das System Sicherheitslücken besitzt (siehe Beschreibung). Wenn Sie wollen, versuchen Sie diese zu finden, und informieren Sie mich. Ansonsten lassen Sie das Hacken lieber.

Der wahre Hacker kann sich gern die Quellen anschauen, mit nach Hause nehmen, und mit einem Haskell-System selbst ausführen.

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de