Folien zur Vorlesung

Hier werden im Laufe des Semesters die Folien zur Vorlesung zur Verfügung gestellt.. Die Folien sind im PDF-Format abgelegt.

1. Einführung

1.1. Organisatorisches

1.2. Motivation

1.3. Empfohlene Literatur

1.4. Alphabete, Wörter, Sprachen

2. Reguläre Sprachen

2.1. Reguläre Ausdrücke

2.2. Endliche Automaten

2.3. Nichtdeterministische endliche Automaten

2.4. Die Potenzmengenkonstruktion

2.5. NFAs mit ε-Übergängen

2.6. Minimale DFAs und der Satz von Myhill-Nerode

2.7. Berechnung des minimalen DFA

2.8. Umwandlung eines Automaten in einen regulären Ausdruck II

2.9 Das Pumping-Lemma

2.10 Entscheidungsprobleme für reguläre Sprachen

3. Kontextfreie Sprachen

3.1 Kontextfreie Sprachen und Grammatiken

3.2 Ableitungsbäume

3.3 Die pre*-Operation

3.4 Entscheidungsprobleme für CFGs

3.5 Normalformen für CFGs

3.6 Chomsky-Normalform

3.7 Greibach-Normalform

3.8 Das Pumping-Lemma für CFLs

3.9 Kellerautomaten

3.10 Deterministische Kellerautomaten

3.11 Abschlusseigenschaften kontextfreier Sprachen

4. Die Chomsky-Hierarchie

5. Prozesse

5.1 Synchronisierte Produkte von Automaten