- Titel: Grundlagen der theoretischen Informatik
- Organisation: LUG JENA
- Seitenzahl: 58
Inhalt
- Inhaltsverzeichnis
- Auflistung der Sätze
- Sätze
- Definitionen und Festlegungen
- I Formale Sprachen
- 1 Sprachen und Grammatiken
- 1.1 Grundlagen
- 1.2 Grammatiken
- 1.3 Die Chomsky-Hierarchie
- 2 Reguläre Sprachen
- 2.1 Endliche Automaten (deterministisch)
- 2.2 Nichtdeterministische endliche Automaten
- 2.3 Reguläre Ausdrücke und Gleichungssysteme
- 2.4 Äquivalenzrelationen und Minimalautomaten
- 2.5 Das Pumping-Lemma
- 2.6 Abschlusseigenschaften
- 3 Kontextfreie Sprachen
- 3.1 Normalformen
- 3.2 Das Pumping-Lemma für kontextfreie Sprachen
- 3.3 Abschlusseigenschaften
- 3.4 Kellerautomaten
- 3.5 Deterministisch kontextfreie Sprachen
- 3.6 Das Wortproblem für kontextfreie Sprachen
- 4 Kontexsensitive und L0-Sprachen
- 4.1 Turingmaschinen
- 4.2 Linear beschränkte Turingmaschinen (LBA)
- 4.3 L0-Sprachen
- II Berechenbarkeit
- 5 Churchsche These
- 5.1 Einführung
- 5.2 Grundlagen
- 5.3 Turing-Berechenbarkeit
- 5.4 Andere Typen von Turing-Maschinen
- 5.5 Die Churchsche These
- 6 Primitv rekursive und partiell rekursive Funktionen
- 6.1 Primitiv rekursive Funktionen
- 6.2 Beispiele für primitiv rekursive Funktionen
- 6.3 Weitere Rekursionsarten
- 6.4 Allgemein rekursive und partiell rekursive Funktionen
- Index
Vorschau
Grundlagen der theoretischen Informatik
Dr. Harald Hempel SS 2006
Inhaltsverzeichnis
I. Formale Sprachen 7
1. Sprachen und Grammatiken 8 1.1. Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2. Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3. Die Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2. Reguläre Sprachen 2.1. Endliche Automaten (deterministisch) . . . . 2.2. Nichtdeterministische endliche Automaten . . 2.3. Reguläre Ausdrücke und Gleichungssysteme . 2.4. Äquivalenzrelationen und Minimalautomaten 2.5. Das Pumping-Lemma . . . . . . . . . . . . . 2.6. Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 14 16 21 26 28 29 30 30 32 34 35 37 39
3. Kontextfreie Sprachen 3.1. Normalformen . . . . . . . . . . . . . . . . . . . 3.2. Das Pumping-Lemma für kontextfreie Sprachen 3.3. Abschlusseigenschaften . . . . . . . . . . . . . . 3.4. Kellerautomaten . . . . . . . . . . . . . . . . . 3.5. Deterministisch kontextfreie Sprachen . . . . . 3.6. Das Wortproblem für kontextfreie Sprachen . .
4. Kontexsensitive und L0 -Sprachen 42 4.1. Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2. Linear beschränkte Turingmaschinen (LBA) . . . . . . . . . . . . . . . . . 44 4.3. L0 -Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
II. Berechenbarkeit
5. Churchsche These 5.1. Einführung . . . . . . . . . . . . . . . 5.2. Grundlagen . . . . . . . . . . . . . . . 5.3. Turing-Berechenbarkeit . . . . . . . . 5.4. Andere Typen von Turing-Maschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .