Die Hauptaufgabe von endlichen Automaten ist das Lesen von Eingabezeichen und die daraus folgende Erstellung einer Ausgabe in Form eines Wortes (Worterkennung).
Ein endlicher Automat (EA) ist ein formales Modell eines Systemes. Der EA kann in einem von endlich vielen Zuständen sein und wird von Zustand zu Zustand durch eine Eingabe bewegt. Was heisst das genau?
Ein EA startet im Anfangszustand und liest das erste Symbol ein. Dieses wird überprüft und veranlasst den EA, in den nächsten Zustand abhängig vom Symbol überzugehen. Wenn der EA einen finalen Zustand erreicht, so akzeptiert er die Eingabe als ein zusammenhängenden String. Zu deutsch: Nach Erhalt eines gegebenen Kommandos werden so lange Zeichen gelesen, bis das nächste Wort erkannt wurde.
Dafür können sogenannte Übergangsdiagramme entworfen werden. Diese Übergangsdiagramme stellen dar, welche Aktionen ausgeführt werden, sobald ein Wort eingelesen wird. Ein Zustand ist als Startzustand gekennzeichnet, dies ist derjenige Zustand, indem sich die Kontrolle am Anfang des Erkennungsprozesses befindet. Mit Zuständen können Aktionen verbunden sein. Diese Aktionen werden ausgeführt, sobald der Kontrollfluss einen entsprechenden Zustand erreicht. Bei Eintritt in einen Zustand wird das nächste Eingabezeichen gelesen. Wenn aus dem aktuellen Zustand ein Weg (Kante) hinausführt, deren Marke dem Eingabezeichen entspricht, so findet ein Übergang in den Zustand statt, auf den die Kante zeigt. Andernfalls ist der Erkennungsprozess gescheitert.
Ein Erkenner für eine Sprache ist ein Programm, das als Eingabe einen Wert x erhält und die Antwort "Ja" liefert, falls x ein Wort der Sprache ist. Andernfalls antwortet es mit "Nein".
Bei endlichen Automaten unterscheidet mensch zwischen nichtdeterministischen endlichen Automaten (NEA) und deterministischen endlichen Automaten (DEA).
Ein NEA akzeptiert einen Eingabestring genau dann, wenn es im Übergangsgraphen einen Pfad vom Anfangszustand zu einem akzeptierenden Zustand gibt, so dass die Kantenmarkierungen entlang dieses Pfades genau die Zeichenfolge x bilden.
Abb. 1*: Ein NEA, der aa*|bb* akzeptiert.
Ein DEA ist ein Spezialfall eines NEA, wobei für jeden Zustand und jede Eingabe höchstens eine mit der Eingabe markierte Kante aus diesem Zustand herausführt. Infolgedessen kann ein DEA sehr leicht entscheiden, ob ein bestimmter Eingabestring akzeptiert wird, denn ausgehend vom Startzustand kann höchstens ein Pfad mit diesem String markiert sein.
Abb. 2**: Ein DEA, der "a", "an", "and", "in", "into" und "to" akzeptiert.
An dieser Stelle möchte ich nicht mehr dazu sagen, da bisher noch niemand mit diesen EA's während des Studiums in Verbindung gekommen ist. Wer sich dafür näher interessiert, sei auf entsprechende Literatur zum Thema verwiesen (siehe Quellenverzeichnis).
* Abbildung aus Aho, Sethi, Ullman: Compilerbau.
** Abbildung aus Frakes, Baezo-Yates: Information Retrieval: Data Structure & Algorithms.
