Überschrift

Was ist ein endlicher Automat?

Ein endlicher Automat ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Man nennt einen Automaten endlich, wenn er eine endliche Menge von Zuständen besitzt, die er einnehmen kann. Ein Zustand speichert die Information über die Vergangenheit, d.h. er reflektiert die Änderungen der Eingabe seit dem Systemstart bis zum aktuellen Zeitpunkt. Ein Zustandsübergang zeigt eine Änderung des Zustandes des endlichen Automaten und wird durch logische Bedingungen beschrieben, die erfüllt sein müssen, um den Übergang zu ermöglichen. Eine Aktion ist die Ausgabe des endlichen Automaten, die in einer bestimmten Situation erfolgt. Bei einem Automaten gelten folgende Bestimmungsstücke:

Jeder Automat muss von außen bedient, d.h. mit Eingabedaten versorgt werden.
Ein Automat befindet sich zu jedem Zeitpunkt in einem bestimmten Zustand. In Abhängigkeit von der Eingabe und dem momentanen Zustand kann er in einen neuen Zustand übergehen.
Der Automat produziert in Abhängigkeit von Eingabe und jeweiligen Zustand gewisse Ausgabedateien.

Eigenschaften eines Automaten

Automaten werden durch bestimmten Funktionen und Mengen beschrieben. Mathematisch kann er so beschrieben werden : A := (E(i), A(i), I, f, g)

A...Automat

E(i)...Eingang

A(i)...Ausgangsmenge

I...Menge interner Zustände

f = E x I --> I -Die Kreuzmenge von E und I wird auf der Menge I abgebildet.

g = E x I--> A -Die Kreuzmenge von E und I wird auf der Menge A abgebildet.

Erstellen eines Automaten

Allgemeines

Wenn man einen einen Automaten entwickeln will, muss man die Eingangsmenge und die Ausgangsmenge beschreiben. Dies erfolgt durch das erstellen einer Tabelle. Dafür benötigt man zwei Tabellen, eine für die Abbildung auf die internen Zustände und eine für die Abbildung auf den Ausgängen.

Abbildung eines Automats

Wir erstellen nun beispielsweise eine Tabelle für den Automaten, der in einer Zeichenkette das Wort „Test“ sucht. Mit „Alle Anderen“ wären alle anderen Zeichen gemeint.

Innerer Zustand/Eingangselemente

	T	e	s	t	Alle anderen
Zustand 0	1	0	0	0	0	Start
Zustand 1	1	2	0	0	0	„T“ gefunden
Zustand 2	1	0	3	0	0	„Te“ gefunden
Zustand 3	1	0	0	4	0	„Tes“ gefunden
Zustand 4	4	4	4	4	4	„Test“ gefunden

Innerer Zustand/Ausgangselemente

	T	e	s	t	Alle anderen
Zustand 0	FALSCH	FALSCH	FALSCH	FALSCH	FALSCH	Start
Zustand 1	FALSCH	FALSCH	FALSCH	FALSCH	FALSCH	„T“ gefunden
Zustand 2	FALSCH	FALSCH	FALSCH	FALSCH	FALSCH	„Te“ gefunden
Zustand 3	FALSCH	FALSCH	FALSCH	WAHR	FALSCH	„Tes“ gefunden
Zustand 4	WAHR	WAHR	WAHR	WAHR	WAHR	„Test“ gefunden

Quellen

http://de.wikipedia.org/wiki/Endlicher_Automat
Buch : Informatik mit Pascal, von Rüdeger Baumann, vom Ernst Klett Verlag

Autoren: Hannes P. und Manuel T.