Definition DEA
Formal definiert man einen deterministischen endlichen Automaten als 5-Tupel (Q, s, Σ, F, σ):
- Q ist eine nicht leere, endliche Menge von Zuständen
- s ∈ Q ist der Startzustand
- Σ ist eine nicht leeres, endliches Eingabealphabet
- F ist die Menge der akzeptierten Endzustände, wobei F eine Teilmenge von Q ist
- σ Q x Σ -> Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.
Ein Fehlerzustand (Fehlersenke) ist ein Zustand, von dem man nicht mehr in einen akzeptierten Endzustand gelangen kann.
Die Menge der Wörter, die vom Automaten akzeptiert werden, also die Wörter, bei denen der Automat in einen akzeptierten Endzustand gelangt, nennt man die vom Automaten akzeptierte Sprache.
Ein Automat heißt deterministisch, wenn für jeden seiner Zustände und für jedes Eingabezeichen nur genau ein Folgezustand existiert. Das Verhalten des Automaten ist somit eindeutig bestimmt.
Ein Wort über dem Alphabet Σ ist eine Endliche Folge von Buchstaben aus Σ.
- Q ist eine nicht leere, endliche Menge von Zuständen
- s ∈ Q ist der Startzustand
- Σ ist eine nicht leeres, endliches Eingabealphabet
- F ist die Menge der akzeptierten Endzustände, wobei F eine Teilmenge von Q ist
- σ Q x Σ -> Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.
Ein Fehlerzustand (Fehlersenke) ist ein Zustand, von dem man nicht mehr in einen akzeptierten Endzustand gelangen kann.
Die Menge der Wörter, die vom Automaten akzeptiert werden, also die Wörter, bei denen der Automat in einen akzeptierten Endzustand gelangt, nennt man die vom Automaten akzeptierte Sprache.
Ein Automat heißt deterministisch, wenn für jeden seiner Zustände und für jedes Eingabezeichen nur genau ein Folgezustand existiert. Das Verhalten des Automaten ist somit eindeutig bestimmt.
Ein Wort über dem Alphabet Σ ist eine Endliche Folge von Buchstaben aus Σ.
Kommentare
Kommentar veröffentlichen