Themen

Skript:
- vl-03a-ft-regularitaet-von-deterministischen-endlichen-automaten-und-nichtdeterministische-endliche-automaten
- vl-03b-ft-determinisierung-von-endlichen-automatene
- vl-03c-ft-nichtdeterministische-endliche-automaten-mit-epsilon-uebergaengen

VL-03a

Wiederholung DFA - bestehend aus 5-Tupel - für jede DFA gibt es eine Grammatik aber nicht für jede Grammatik eine DFA
Widerholung DFAs
Definition

Ein deterministischer endlicher Automat (deterministic finite automaton, DFA) ist ein 5-Tupel $M = (Z, Σ, δ, z_{0}, E)$ , wobei:
- $Z$ ist eine endliche Menge von Zuständen
- $Σ$ ist das (endliche) Eingabealphabet mit $Z \cap Σ = \emptyset$
- $δ : Z \times Σ \to Z$ ist die (totale) Überführungsfunktion
- $z_{0} \in Z$ ist der Startzustand
- $E \subseteq Z$ ist die Menge der Endzustände.
Konstruktion einer regulären Grammatik
Akzeptierte Sprachen von DFAs ist regulär
Wird jede Sprache durch ein DFA akzeptiert?
- Für die Beantwortung dieser Frage brauchen wir NFAs (nichtdeterministische endliche Automaten)
Nichtdeterministisische endliche Automaten
- Automat darf mehrere Wege für ein Buchstaben haben
- Darf diesen willkürlich aussuchen
- machen Konstruktionen einfacher
Verwerfender Lauf bedeutet nicht, dass Wort nicht drin ist in Sprache, sonder der Lauf es nicht gefunden hat
```
graph LR
id1((z)) --a--> id2((z1))
id1((z)) --a--> id3((z2))
```
Akzeptanz bei NFAs
- NFA wird akzeptiert, sobald es vom Startzustand einen Pfad zu einem Endzustand gibt
$δ \sim$ - Funktion
- Akzeptierte Sprache des Beispiels
Läufe von NFAs
- Definition
- Konstruktion von NFAs basierend von Sprachen (S.19)

NFA und DFA stellen die gleiche reguläre Sprache dar, NFAs nur einfacher als DFAs
NFAs und ihre Rolle in der Akzeptanz regulärer Sprachen
- Beispiel für
Potenzmengenkonstruktion zur Transformierung von NFAs in DFAs
Theoretische Grundlagen und Beweise zur Determinisierung
Beispiele für die Konstruktion von NFAs aus regulären Grammatiken
Analyse der Komplexität und Größe von Automaten in Bezug auf Zustände und Übergänge
Knotenanzahl:
- NFA: $2 n - 1$
- DFA: $2^{n}$