Informatik: Theoretische Informatik; Weilburg XII/111 Automaten mit Prolog Peter G. Poloczek

Informatik: Theoretische Informatik; Weilburg XII/11 1

Automaten mit Prolog

Peter G. Poloczek

Zu Prolog: Lehrplan Informatik 1

• „Im Leistungskurs lernen die Schülerinnen und Schüler mindestens eine weitere Programmiersprache mit prädikativem oder funktionalem Sprachparadigma kennen. Der Einsatz von Prolog wird durch geeignete Unterrichtsmaterialien auf dem Hessischen Bildungsserver unterstützt….“

• Deklarative Programmiersprache


Zu Prolog: Lehrplan Informatik 2

• Q4: Wahlthema: Prolog als Sprache der künstlichen Intelligenz

• „In diesem Kurs kann – sofern noch nicht an einer anderen Stelle geschehen – die Behandlung einer zweiten Programmiersprache mit einem nicht imperativen Sprachparadigma erfolgen. Prolog bietet sich als deklarative Sprache aus mehreren Gründen an…“


Materialien zu Prolog

• Auf dem Bildungsserver (http://dms.bildung.hessen.de/), genauer:

• http://lakk.bildung.hessen.de/netzwerk/faecher/informatik/prolog.html

• Buch 12 €

• Es gibt eine CD dazu

• Auszug: herzlichen Dankan den Autor G. Röhner


Automaten - Einstieg

• Kap. 18.1 und 18.2: Technische Automatik

• Kap. 18.3: Automaten aus der Theor.Inf.– Zustandsdiagramme– Syntaxdiagramme

• Kap. 18.4: Definition Endlicher Automat– Eingabealphabet, Ausgabealphabet– Zustände, Anfangszustand, Endzustand– Übergangsfunktion


Umsetzung in Prolog – 18.5

• Member-Prädikat:

• Eingesetzt (mindestens) bei:– Eingabe, Ausgabe, Zustand

• Beispiel:eingabe(X):- member(X, [f, h, c, l, k]).

• Definition von Anfags- und Endzustand:– anfangszustand(0). – endzustand(0).


Umsetzung in Prolog: Übergänge

• % uebergang(+Zustand, +Eingabe, -Ausgabe, -NeuerZustand])

• uebergang(Zustand, f, -, NeuerZustand):- Zustand =< 100, NeuerZustand is Zustand + 50, !.

• (Hinweis: Der „Cut“ (!) verhindert die Suche nach alternativen Lösungen.)

• uebergang(150, f, f, 150):- !. • uebergang(Zustand, h, -, NeuerZustand):-

Zustand =< 50, NeuerZustand is Zustand + 100, !.


Vorgehensweise - 1

• Die angegebenen Komponenten bestimmen einen speziellen endlichen Automaten.

• Die Arbeitsweise hingegen ist für alle Automaten gleich.– Der Automat wird in den Anfangszustand gesetzt.– Dann liest er ein Zeichen, führt den durch Zustand

und gelesenes Zeichen bestimmten Zustandsübergang durch und gibt dabei das Ausgabezeichen aus.


Vorgehensweise - 2

• Dies macht er solange, wie noch Eingabezeichen da sind.

• Wenn sich nach Abarbeitung der Eingabe der Automat in einem Endzustand befindet, so hat er die Eingabe akzeptiert.


Steuerprädikat: automat

• Eine Klausel startet den Automaten• Eine zweite Klausel führt die Arbeitsschritte

aus • Mit der dritten Klausel beendet der Automat

seine Arbeit• Zur Vereinfachung der Eingabe setzen wir

das Systemprädikat atom_chars/2 ein, das ein eingegebenes Atom in eine Liste der Zeichen zerlegt


Präd. automat: Start

• automat(Eingabe):- anfangszustand(Zustand), atom_chars(Eingabe, Liste), automat(Zustand, Liste).


Präd. automat: Arbeitsschritte

• automat(Zustand, [Eingabe|Rest]):- uebergang(Zustand, Eingabe, Ausgabe, NeuerZustand), write(Zustand), tab(2), write(Eingabe), write(' -> '), write(Ausgabe), tab(2), writeln(NeuerZustand), automat(NeuerZustand, Rest).


Präd. automat: Ende+ Beispiel

• automat(Zustand, []): endzustand(Zustand).

• Beispielhafter Aufruf: ?- automat(ffkfhflk).


Getränkeautomat

• Eingaben : 50 Ct (F), 1 € (H),Colataste (C), Limotaste (L), Korrekturtaste (K)

• Ausgaben: 50 Ct (F), 1 € (H),1,50 € (G), Cola (C) Limo (L), nichts (-)


Präd. automat: Ablauf

• ?- automat(ffkfhflk).• 0 f -> - 50• 50 f -> - 100• 100 k -> h 0• 0 f -> - 50• 50 h -> - 150• 150 f -> f 150• 150 l -> l 0• 0 k -> - 0• true


Modellierung von Akzeptoren

• Bei erkennenden endlichen Automaten entfällt das Ausgabealphabet.

• Die Übergangsfunktion liefert zu einem Zustand und einem Eingabezeichen nur den Folgezustand.

• Das Argument Ausgabe fällt also weg und das Prädikat uebergang wird dreistellig:

• % uebergang(+Zustand, +Eingabe, -FolgeZustand)


Nützliche Systemprädikate

• Mit Hilfe der Systemprädikate is_alpha und is_alnum lässt sich feststellen, ob ein Buchstabe (groß oder klein) bzw. ein alphanumerisches Zeichen (Buchstabe oder Ziffer) vorliegt

• is_digit überprüft, ob eine Ziffer vorliegt


Weitergehendes

• Kap 18.7: Erzeugte Sprache - ein Graphenproblem

• Kap. 18.8 Nichtdeterministischer endlicher Automat

• Kap. 18.9 Automaten mit ε-Übergängen

• Kap. 18.10 Reguläre Ausdrücke

• ……

• Kap. 18.13 Alternative Zugänge


Quellen und Materialien• http://lakk.bildung.hessen.de/netzwerk/faecher/informatik/prolog.html• Gerhard Röhner: Informatik mit Prolog; 3. vollständig neu überarbeitete Auflage,

Frankfurt, 2007.; ISBN 3-88327-499-2(Auszug Kap. 18 anbei)

• http://classes.soe.ucsc.edu/cmps112/Spring03/languages/prolog/PrologIntro.pdf(als PDF anbei)

• „How-to“: http://www.cs.ucl.ac.uk/staff/mahmed/teaching/intro.html• IKF-Material: http://ikf.ers1.de/wb07/Prolog%20im%20LK%20Informatik.pdf



Vielen Dank für die Aufmerksamkeit!

Aufgaben:

• Starten sie die Prolog-Umgebung und testen Sie das Programm „Getränkeautomat“

• Testen Sie die drei Beispiele aus 18.13• Bauen Sie eines oder mehrere der Code-

Elemente von 18.6 bis 18.9 in das System• ein.• Bearbeiten Sie einige der Aufgaben aus 18.16.


Documents

Informatik: Theoretische Informatik; Weilburg XII/111 Automaten mit Prolog Peter G. Poloczek