- Allgemeines
- Berechenbarkeit
- Entscheidbarkeit
- Wortproblem
- Charakteristische Funktion
- Entscheidbarkeit
- Zusammenhang zwischen Entscheidbarkeit und Semientscheidbarkeit
- Rekursive Aufzählbarkeit
- Halteproblem
- Die Sprache des Halteproblems und des speziellen Halteproblems
- Satz: Das Halteproblem ist unentscheidbar
- Informeller Beweis des Halteproblems mittels Halteproblemtabelle
- Das Halteproblem ist Semientscheidbar
- Spezielles Halteproblem
- Reduktion
- Reduktionsprinzip
- Unentscheidbarkeit des Halteproblems
- Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Satz
- Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Informell
- Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Formal
- Andere unentscheidbare Probleme
- Nichtdeterminismus (Ergänzung)
- Komplexitätsklassen
- NPC Beweise
- Die große Frage der Informatiker P=NP oder P
NP?
- Polynomielle Reduzierbarkeit
- NP-hart, NP-vollständig
- Aussagelogik
- Satz von Cook
- Prinzipielle Techniken für NP-Vollständigkeitsbeweise
- Einige NP-Vollständigkeitsbeweise
- coNP
- PSPACE-Vollständigkeit
- Zusammenfassung
- Die große Frage der Informatiker P=NP oder P
- Praktischer Einsatz von formalen Sprachen: Compiler
- Grammatiken
- Definitionen
- Chomsky Hierarchie
- Inklusion der Chomskyhierarchie
- Grafische Darstellung der Chomskyhierarchie
- Transformation um die
-Freiheit bis auf
in Typ 1 herzustellen
- Abschlußeigenschaften
- Sprachen vom Typ 0
- Kontextsensitive Sprachen - Typ 1
- Wortproblem für Typ 0 und Typ 1 Sprachen
- Reguläre Sprachen
- Endliche Automaten
- Endliche Automaten und reguläre Grammatiken
- Verknüpfungen regulärer Sprachen
- Algorithmen zur Feststellung von Eigenschaften
- Pumping Lemma für reguläre Sprachen
- Reguläre Ausdrücke
- Syntaxdiagramme
- Zusammenfassung
- Minimierung von endlichen Automaten
- Kontextfreie Sprachen (CFG)
- Ableitungsbaum
- Nutzlose Variablen
- Chomsky Normalform (CNF)
- CYK-Algorithmus für das Wortproblem
- Pumping Lemma für kontextfreie Sprachen
- Abschlußeigenschaften
- Griebach Normalform
- Kellerautomaten
- Definition: Nichtdeterministischer Kellerautomat (NKA)
- Konfiguration, Notation der Übergangsfunktion und Konfigurationswechsel
- Akzeptanzverhalten
- Akzeptanz durch Endzustand
Akzeptanz durch leeren Keller
- Akzeptanz durch leeren Keller Akzeptanz durch Endzustand
- Kontextfreie Grammatik NKA
- NKA kontextfreie Grammatik
- NKAs mit zwei Kellern
- reguläre Sprache
kontextfreie Sprache = kontextfreie Sprache
- Deterministische kontextfreie Sprachen
- Eigenschaften
- Deterministische Kellerautomaten (DKAs)
- Akzeptanzbedingungen
- Präfixeigenschaft
- Beispiele
- Komplettes Schaubild der Chomskyhierarchie
- Abschlußeigenschaften
- LR(0)-Grammatiken
- Einleitung zu LR(k)-Grammatiken
- Eigenschaften von LR(0)-Grammatiken
- Begriffsdefinition: Reduktion
- Definition LR(0)-Grammatik
- Definition von Begriffen für eine verbale Definition von LR(0)-Grammatiken
- Verbale Definition von LR(0)-Grammatik
- Eindeutigkeit
- Präfixeigenschaft
- Nichtdeterministischer LR(0)-Parser
- Tabellarische Aufführung der Abschlußeigenschaften verschiedener Sprachtypen
Turingmaschine
entscheidbar, dann auch 
entscheidbar
EXPTIME
PSPACE
3SAT (lokale Ersetzung)
