Automaten in Prolog
Inhaltsverzeichnis
Ein Vorteil der Modellierung von Automaten in Prolog besteht darin, dass Prolog selbst auf der Basis von Backtracking und Rekusion arbeitet. Daher eignet sich Prolog besonders für NEA und NEA mit 
-Übergängen, die sich ja bekanntlich weniger effektiv in imperativen Programmiersprachen wie Pascal oder Java umsetzen lassen.
Automat mit Ausgabe (Transduktor)
Gegeben ist der Zustandsgraph für einen Getränkeautomaten, der Limo oder Cola liefern kann. Um diesen Automaten in Prolog zu modellieren genügt es, dessen Komponenten in geeigneten Prädikaten zu definieren:
eingabe(X):- member(X,[f,h,c,l,k]). ausgabe(X):- member(X,[-,f,h,g,c,l]). zustand(X):- member(X,[0,50,100,150]). anfangszustand(0).
Die Definition des Eingabe- und Ausgabealphabets sowie der Zustandsmenge ist hier allerdings nur notwendig, wenn diese in den folgenden automat-Klauseln Verwendung finden.
Die notwendige Übergangs- und Ausgabefunktion lassen sich mit Hilfe eines Prädikats definieren. In einzelnen Fällen lassen sich Klauseln zusammenfassen. Da in diesem Fall ein deterministischer Automat vorliegt, muss nachdem eine Lösung gefunden wurde nicht weiter gesucht werden ... daher wird durch den Cut das Backtracking unterbunden.
/* uebergang(+Zustand, +Eingabe, -Ausgabe, -NeuerZustand]) */ uebergang(0, f, -, 50):- !. uebergang(50, f, -, 100):- !. uebergang(100, f, -, 150):- !. uebergang(150, f, f, 150):- !. uebergang(Zustand, h, -, NeuerZustand):- Zustand =< 50, NeuerZustand is Zustand + 100, !. uebergang(Zustand, h, h, Zustand):- !. uebergang(Zustand, c, -, Zustand):- Zustand =< 100, !. uebergang(150, c, c, 0):- !. uebergang(Zustand, l, -, Zustand):- Zustand =< 100, !. uebergang(150, l, l, 0):- !. uebergang( 0, k, -, 0):- !. uebergang( 50, k, f, 0):- !. uebergang(100, k, h, 0):- !. uebergang(150, k, g, 0):- !.
Damit ist dieser spezielle Automat definiert. Die Arbeitsweise hingegen ist für alle Automaten gleich. Daher findet das hier dargestellte Prädikat bei der Modellierung aller Transduktoren Anwendung.
automat(Eingabe):-
anfangszustand(Zustand),
automat(Zustand, Eingabe).
automat(Zustand, [Eingabe|Rest]):-
uebergang(Zustand, Eingabe, Ausgabe, NeuerZustand),
write(Zustand), tab(2),
write(Eingabe), write(' -> '),
write(Ausgabe), tab(2),
write(NeuerZustand), nl,
automat(NeuerZustand, Rest).
automat(Zustand, []).
Der Automat wird in den Anfangszustand gesetzt. Dann liest er ein Zeichen ein, führt den definierten Zustandsübergang durch und gibt das entsprechende Ausgabezeichen aus. Dies wiederholt er solange, wie noch Eingabezeichen (in der zu Beginn übergebenen Liste) da sind.
Automat ohne Ausgabe (Akzeptor)
Die Modellierung eines Akzeptors funktioniert analog der oben beschrieben Modellierung eines Transduktors. Allerdings benötigen wir hier keine Ausgabe (und kein Ausgabealphabet), dafür müssen Endzustände definiert werden. Die automat-Klauseln werden etwas vereinfacht, da keine Ausgabe mehr erfolgt; das uebergang-Prädikat wird dreistellig.
endzustand(0).
automat(Wort):-
anfangszustand(Zustand),
atom_chars(Wort, Liste),
automat(Zustand, Liste).
automat(Zustand, [Eingabe|Rest]):-
uebergang(Zustand, Eingabe, NeuerZustand),
write(Zustand), tab(2),
write(Eingabe), write(' -> '),
write(NeuerZustand), nl,
automat(NeuerZustand, Rest).
automat(Zustand, []):-
endzustand(Zustand).
In diesem Beispiel wurde die Eingabe für den User etwas einfacher gestaltet. Durch Verwendung des Prädikats atom_chars, welches aus einem Eingabestring eine Eingabeliste generiert, können nun ganze Strings eingegeben werden.
Nichtdeterministische endliche Automaten (NEA)
Da Prolog automatisch mti Backtracking arbeitet, werden NEA analog zu Akzeptoren programmiert, d.h. die automat-Klauseln bleiben identisch. Lediglich bei den uebergang-Klauseln lässt man die Cuts weg, damit nach alternativen Lösungen gesucht werden kann.
Nichtdeterministische endliche Automaten mit -Übegängen (-NEA)
Auch diese Automaten werden in Prolog ähnlich den Akzeptoren programmiert. Lediglich die -Übergänge müssen gesondert behandelt werden, weil sie kein Eingabezeichen benötigen. Daher müssen die beiden bisherigen automat/2-Klauseln um jeweils eine -Variante ergänzt werden.
/* normaler eps-Uebergang */
automat(Zustand, [Eingabe|Rest]):-
eps_uebergang(Zustand, NeuerZustand),
write(Zustand), tab(2),
write(eps), write(' -> '),
write(NeuerZustand), nl,
automat(NeuerZustand, [Eingabe|Rest]).
/* eps-Uebergaenge in den Endzustand */
automat(Zustand, []):-
eps_uebergang(Zustand, NeuerZustand),
write(Zustand), tab(2), write(eps), write(' -> '),
write(NeuerZustand), nl,
automat(NeuerZustand, []).
Die zum Automaten gehörenden -Übergänge müssen dann z.B. so programmiert werden:
eps_uebergang(z0,z1). eps_uebergang(z1,z2).
Erzeugen von Sprachen
Um die Menge der von einem Akzeptor A erzeugten Worte zu erkennen, sind die oben angegebenen Klauseln nicht geeignet. Die Bestimmung der von einem Automaten erzeugten Sprache kann als Suche nach allen Wegen im Zustandsgraphen gedeutet werden. Probleme könnten dann jedoch immer noch Zyklen, z. B. in NEA's mit -Übergängen, bereiten, da hier der Graph erst in einer (unendlichen) Tiefe durchsucht wird. Daher muss der Graph in seiner Breite durchsucht werden, d. h. es werden erst alle Pfade der Länge 1, dann alle Pfade der Länge 2 usw. gesucht, die vom Anfangs- in den Endzustand führen.
Die folgenden Klauseln erzeugen die Sprache eines Automaten mit dem Aufruf der Klausel erzeugteSprache(X)..
/* erzeugte Sprache */ erzeugteSprache(Wort):- anfangszustand(ZustandA), mehrfachuebergang(ZustandA, Liste, ZustandZ), endzustand(ZustandZ), atom_chars(Wort, Liste). einfachuebergang(Zustand, Eingabe, Neuzustand):- alphabet(Eingabe), uebergang(Zustand, Eingabe, Neuzustand). mehrfachuebergang(Zustand, [Eingabe], Neuzustand):- einfachuebergang(Zustand, Eingabe, Neuzustand). mehrfachuebergang(Zustand, [Kopf|Rest], Neuzustand):- mehrfachuebergang(Zwischenzustand, Rest, Neuzustand), einfachuebergang(Zustand, Kopf, Zwischenzustand).
