Informatikmaterialien  von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |

	Richard-Wossidlo-Gymnasium Ribnitz-Damgarten Fachbereich Informatik

Endliche Automaten mit Ausgabe

Aus der Überlegung zu realen Automaten definiert man den endlichen abstrakten Automaten. Seine Benutzung führt in das Teilgebiet "Automatentheorie" der theoretischen Informatik.

Abstraktion realer Automaten 

Soll unabhängig von einer Implementierung der Automat modelliert werden, so benötigt man folgende Bestandteile:

• Eingabemedium
  z. B. ein Band bestimmter Länge, das die Eingaben einzeln (feldweise) enthält

• Ausgabemedium
  z.B. ein geschlossenes Band, dass die Ausgabeelemente feldweise erfasst

• Zentraleinheit
  zur Steuerung des Automaten und zur Speicherung der inneren Zustände 

• Lesekopf
  zum Lesen des Eingabebandes

• Schreibkopf 
  zum Schreiben auf das Ausgabeband

1. Mealy-Automat 

Der Mealy-Automat lässt sich aus der Verallgemeinerung der Analyse realer Automaten ableiten.

Ein Mealy-Automat A = (X, Y, Z, δ, λ, z0) ist ein endlicher Automat mit Ausgabe. Dabei gilt: X ... das Eingabealphabet (nichtleere, endliche Menge)  Y ... das Ausgabealphabet (nichtleere, endliche Menge) Z ... die Zustandsmenge (nichtleere, endliche Menge) δ: X × Z Z ist die Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) einen Folgezustand zuordnet λ: X × Z Y ist die Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) ein Ausgabezeichen zuordnet z0 Z ist der Anfangszustand

2. Transduktor

Ein Transduktor A = (X, Y, Z, δ, λ, z0) ist ein veränderter Mealy-Automat, dessen Ausgabefunktion wie folgt definiert wird: λ: X × Z Y* ist die Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) ein Ausgabewort zuordnet.

Man beachte den feinen Unterschied zwischen den beiden Automatendefinitionen: 
Y* ist die Menge aller endlichen Folgen aus Y einschließlich des leeren Wortes $ (manchmal auch ε). 

Die Elemente von X nennt man Eingabezeichen, die von Y Ausgangszeichen, die von Z Zustände. Die Angabe der Überführungs- und Ausgabefunktion erfolgt üblicherweise in Tabellen oder mit Hilfe des Zustandsdiagramms.

Beispiel – Parkscheinautomat

Auf einem Parkplatz kostet das Parken ohne Zeitbegrenzung 2,00 €. Nach Einwurf der korrekten Geldsumme wird ein Parkschein gedruckt. Der Automat wechselt nicht, gibt zu viel gezahltes Geld nicht zurück und hat keine Möglichkeit des Abbruchs. 

Der Parkscheinautomat hat das 6-Tupel A = (X, Y, Z, δ, λ, z0) mit

• Eingabealphabet X = {x₅₀, x₁₀₀, x₂₀₀}

• Ausgabealphabet Y = {y_s}

• Zustandsmenge Z  = {z₀, z₅₀, z₁₀₀, z₁₅₀}

• Überführungsfunktion δ: X × Z → Z 

δ	z0	z50	z100	z150
x50	z50	z100	z150	z0
x100	z100	z150	z0	z0
x200	z0	z0	z0	z0

• Ausgabefunktion λ: X × Z → Y*  = {ε, y_s, y_sy_s, ...}

λ	z0	z50	z100	z150
x50	ε	ε	ε	ys
x100	ε	ε	ys	ys
x200	ys	ys	ys	ys

• z0 ist der Anfangszustand

Abstraktion des Parkscheinautomaten in PROLOG

Es soll nun der oben beschriebene Parkscheinautomat mit Hilfe der Programmiersprache PROLOG modelliert werden. Folgende Schritte sind dazu notwendig (nach Röhner):

1. Festlegen der Ein- und Ausgabeobjekte und der möglichen Zustände:

eingabe(X):- member(X, [fuenfzig, eins, zwei]).
ausgabe(Y):- member(Y, [parkschein]).
zustand(Z):- member(Z, [0, 50, 100, 150]).
%zustand(0) bedeutet: kein Geld eingeworfen
%zustand(50) bedeutet: 50 Cent eingeworfen, usw.

2. Hilfsfunktion zur Prüfung der Zugehörigkeit zur Ausgabemenge Y*:

ausgabemenge([]).
ausgabemenge([K|Rs]):- ausgabe(K),ausgabemenge(Rs).

3. Festlegen des Start- und Endzustandes:

anfangszustand(0).
endzustand(0).

4. Definieren der Übergangsfunktion:

% uebergang/4 wird definiert durch uebergang(ausgangszustand, eingabe, ausgabe, folgezustand)
uebergang(0, fuenfzig, [], 50):-!.
uebergang(0, eins, [], 100):-!.
uebergang(0, zwei, [parkschein], 0):-!.
uebergang(50, fuenfzig, [], 100):-!.
uebergang(50, eins, [], 150):-!.
uebergang(50, zwei, [parkschein], 0):-!.
uebergang(100, fuenfzig, [], 150):-!.
uebergang(100, eins, [parkschein], 0):-!.
uebergang(100, zwei, [parkschein], 0):-!.
uebergang(150, fuenfzig, [parkschein], 0):-!.
uebergang(150, eins, [parkschein], 0):-!.
uebergang(150, zwei, [parkschein], 0):-!.

5. Programmbeiwerk

start(Eingabe):- 
  anfangszustand(Zustand),
  write('Eingabe -> Ausgabe'),
  nl,
  automat(Zustand, Eingabe).

automat(Zustand, [Eingabe|Rest]):-
  eingabe(Eingabe),                                      % Prüfen der Eingabe
  uebergang(Zustand, Eingabe, Ausgabe, NeuerZustand),    % Übergang
  zustand(NeuerZustand),                                 % Prüfen des Zustandes
  ausgabemenge(Ausgabe),                                 % Prüfen der Ausgabe
  write(Eingabe), write(' -> '),
  write(Ausgabe), tab(2),
  nl,
  automat(NeuerZustand, Rest).

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

Anfragen an den Automaten erfolgen über die Eingabe ?- start([eingabe,eingabe,...]).

Vergleich zwischen endlichen Automaten und Computer

Der Computer folgt dem EVA-Prinzip. Die über die Tastatur vorgenommene Eingabe wird von der Zentraleinheit verarbeitet. Dazu benötigt sie einen Algorithmus. Dieser muss in der Zentraleinheit hinterlegt sein und wird in Abhängigkeit von der Belegung der Speicherzellen und Register erfolgen. Es gibt also Übergänge zwischen verschiedenen Zuständen. Einsprechend des Algorithmus erfolgen Ausgaben.

Das abstrakte Modell des endlichen Automaten mit Ausgaben erfasst die wesentlichen Aspekte eines Computers.

zur Startseite

© Tino Hempel 1997 - 2009

Im Web vertreten seit 1994. Eine Internet-Seite aus dem Angebot von Tino Hempel.