Endliche Automaten?

Überprüft, ob eine Zeichenkette zu einer Sprache gehört / syntaktisch richtig ist

Kann nur Syntax und keine Semantik prüfen

- Eingabealphabet
- endliche Menge an Zuständen
- Startzustand
- Endzustand/-zustände
- Zustandsübergänge

(Man startet dort) Zeichenkette wird von links nach rechts verarbeitet.

-> Aktuell gelesenes Zeichen -> Folgezustand
gibt es keinen passenden Übergang für ein Zeichen, so bricht die Verarbeitung ab

Bei jedem Übergang verkürzt sich die Länge der Zeichenkette um 1

Wenn die Verarbeitung nicht abgebrochen wurde und sich der Automat nach vollständiger Abarbeitung im Endzustand befindet, gehört die Zeichenkette zur formalen Sprache

Den Fangzustand. Dorthin führen Übergänge für Zeichen, für die es keinen passenden Übergang in einen anderen Zustand gibt und daher verraten werden. Der Fangzustand kann nicht mehr verlassen werden.

Man bewertet sie als:
- Endlich
- Erkennend
- Vollständig
- Nichtdeterministisch

Die Verarbeitung einer Zeichenkette endet in einem Endzustand oder wird abgebrochen.

Verarbeitet eine beliebig lange Zeichenkette und entscheidet am Ende ob sie akzeptiert wird -> Endzustand

In jedem Zustand gibt es für jedes Zeichen des Alphabets einen Zustandsübergang

Automat, bei dem mindestens ein Zustandsübergang nicht eindeutig ist, weil von einem Zustand aus mehrere Folgezustände für dasselbe Zeichen möglich sind
-> Gegenteil: DETERMINISTISCHER Automat