Suche Home Einstellungen Anmelden Hilfe  

3.2.1 Formale Darstellung Endlicher Automaten, Deterministische EA

Definition EA-formal

Erweiterte Übergangsfunktion
delta-dach

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.

Üben mit dem JFLAP-Tool

Endliche Automaten als Graphen 1   2   3   4   5 Nicht-deterministische Endliche Automaten

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: