1Was macht ein Automat?
Überprüft, ob eine Zeichenkette zu einer Sprache gehört / syntaktisch richtig ist
2Was ist das Drawback bei einem Automaten (was kann er nicht)?
Kann nur Syntax und keine Semantik prüfen
3Woras besteht ein Automat?
- Eingabealphabet
- endliche Menge an Zuständen
- Startzustand
- Endzustand/-zustände
- Zustandsübergänge
4Was passiert beim Startzustand (1.)?
(Man startet dort) Zeichenkette wird von links nach rechts verarbeitet.
5Was passiert beim Zustandsübergang (2.)?
-> Aktuell gelesenes Zeichen -> Folgezustand
gibt es keinen passenden Übergang für ein Zeichen, so bricht die Verarbeitung ab
6Was passiert bei jedem Übergang (3.)?
Bei jedem Übergang verkürzt sich die Länge der Zeichenkette um 1
7Was passiert beim Endzustand (4.)?
Wenn die Verarbeitung nicht abgebrochen wurde und sich der Automat nach vollständiger Abarbeitung im Endzustand befindet, gehört die Zeichenkette zur formalen Sprache
8Welchen Zustand gibt es noch und was ist seine Funktion?
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.
9Wie bewertet man Automaten?
Man bewertet sie als:
- Endlich
- Erkennend
- Vollständig
- Nichtdeterministisch
10Was bedeutet dass ein Automat ENDLICH ist?
Die Verarbeitung einer Zeichenkette endet in einem Endzustand oder wird abgebrochen.
11Was bedeutet dass ein Automat ERKENNEND ist?
Verarbeitet eine beliebig lange Zeichenkette und entscheidet am Ende ob sie akzeptiert wird -> Endzustand
12Was bedeutet dass ein Automat VOLLSTÄNDIG ist?
In jedem Zustand gibt es für jedes Zeichen des Alphabets einen Zustandsübergang
13Was bedeutet dass ein Automat NICHT DETERMINISTISCH ist?
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