Definition
 |
Erweiterte Übergangsfunktion
 |
Sprache des EA
|
|
Welche Komponenten eines EA müssen in einer Definition erfasst werden?
Der Automat erkennt Zeichen und er hat Zustände.
Ein Übergang von einem Zustand in einen anderen Zustand ist möglich.
Das Wissen, unter welchen Bedingungen so ein Übergang stattfinden kann, wird durch die Übergangsfunktion repräsentiert.
Außerdem muss deutlich werden, in welchem Zustand sich der Automat am Anfang einer Analyse befindet und in welchen Zuständen
er die Analyse erfolgreich beenden kann.
Der Lesekopf braucht keine Extra-Repräsentation, da sich seine Aktionen auf ein schrittweises Lesen des Eingabebandes beschränken.
Somit kann ein EA durch ein Quintupel definiert werden.
Die Übergangsfunktion ist eine partielle Abbildung. Sie ordnet einem Paar <Zustand, Eingabezeichen> einen <Zustand> zu.
Der Automat interpretiert eine Zuordnung (q, 'xylophon') nach (p) folgendermaßen:
Wenn ich im Zustand q bin und der Lesekopf das Zeichen 'xylophon' liest, so kann ich in den Zustand p wechseln und
den Lesekopf eine Zelle weiter schieben.
Diese Übergangsfunktion kann auf Zeichenketten erweitert werden.
Mit dieser Erweiterten Übergangfunktion, kann auch die Sprache des Automaten angegeben werden:
Zur Sprache des EA gehören alle Zeichenketten w, für die es einen (erweiterten) Übergang (q,w) nach p gibt,
wobei q der Startzustand und p ein Endzustand ist.
|
1
2
3
4
5
Nicht-deterministische Endliche Automaten