Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Akzeptoren – 
Endliche Automaten ohne Ausgabe


Wiederholung Parkscheinautomat

Der von uns modellierte Parkscheinautomat besitzt nur zwei Ausgabeelemente, nämlich "nichts" und "Parkschein". Wir verändern die Situation so, dass der Parkschein gedruckt, wenn der Benutzer genau 2 € eingeworfen hat, wobei nur 50 Cent-Münzen akzeptiert werden, restliches Geld wird ignoriert.
Damit der Automat von "nichts tun"-Zustand in den "Parkschein"-Zustand wechselt, muss Geld in der richtigen Wertigkeit eingeworfen werden. Der Automat muss den korrekten Geldwert erkennen und, um den Schein zu drucken, diesen Zustand akzeptieren

Modellierung 

Werden vier 50-Cent-Münzen eingeworfen (f), so akzeptiert dies der Automat (Zustand z4). Denn nur der Zustand z4 ist ein End- und damit Akzeptierzustand.

Definition 

Ein erkennender endlicher Automat (Akzeptor) A = (X, Z, δ, z0, ZE) wird definiert durch:

  • X ist eine nichtleere, endliche Menge – das Eingabealphabet

  • Z ist eine nichtleere, endliche Menge – die Zustandsmenge

  • δ: X × Z → Z ist die Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) einen Folgezustand zuordnet

  • z0 ∈ Z ist der Anfangszustand
  • ZE⊆ Z ist die Menge der Endzustände.

Er entspricht also im Wesentlichen dem abstrakten Automat, nur das der Schreibkopf und das Ausgabeband fehlen.

Sprache des Automaten 

Gelangt der Automat in den Akzeptierzustand, so wird die dazu notwendige Eingabefolge als ein Wort des Automaten bezeichnet. Die Menge aller akzeptierten Eingabefolgen, die man Wörter nennt, bezeichnet man als Sprache des Automaten L(A). 

Die Sprache eines Automaten L(A) ist die Menge aller von ihm akzeptierten Wörter über dem Eingabealphabet X.

L(A) = {w | w  X* und δ*(w, z0 ZE}, wobei gilt:

  • w ist ein Eingabewort über dem Alphabet X,
  • δ* ist eine Folge von Überführungsfunktionen, die beginnend im Startzustand z0 mit dem Eingabewort w den Automaten in einen Endzustand überführen. 

Beispiele 

Aufgabe: Es ist ein Akzeptor zu konstruieren, der folgendes erkennt: ha!, haha!, hahaha! usw.  

Lösung:

X = {h, a, !},  damit gilt für X* = {ε, h, a, !, hh, ha, h!, ah, aa, a!, !h, !a, !!, hhh, hha, ...}
Z = {z0, z1, z2, z3, z4},
ZE = {z3}

Lachautomat

Modellierung in PROLOG:

% Start- und Endzustände festlegen
start(1).
ende(4).

% Überführungsfunktion delta festlegen
% Überführungsfunktionen zum Zustand 5 
% müssen nicht implementiert werden (Warum eigentlich? ;) )
delta(1, h, 2).
delta(2, a, 3).
delta(3, h, 2).
delta(3, '!', 4).

% Prüfen, ob Zeichenkette
%  (1) der Startzustandsbedingung genügt
%  (2) den restlichen Bedingungen genügt
akzeptiert(String) :- start(Startzustand), pruefer(Startzustand, String).

pruefer(Zustand, []) :- ende(Zustand).
pruefer(Zustand, [Zeichen|Restzeichen]) :- delta(Zustand, Zeichen, NeuerZustand), pruefer(NeuerZustand, Restzeichen).

Der Automat akzeptiert alle Wörter der geforderten Gestalt. Er ist also in der Lage, die Sprache L(A) = {(ha)n! | n > 0} zu erkennen.



zur Startseite
© Tino Hempel 1997 - 2009 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.