Nächste Seite: Allgemeines Aufwärts: Hauptseite Theorie Vorherige Seite: Hauptseite Theorie
Inhalt
- Allgemeines
- Berechenbarkeit
- Entscheidbarkeit
- Wortproblem
- Charakteristische Funktion
- Entscheidbarkeit
- Zusammenhang zwischen Entscheidbarkeit und Semientscheidbarkeit
- Rekursive Aufzählbarkeit
- Halteproblem
- Andere unentscheidbare Probleme
- Nichtdeterminismus (Ergänzung)
- Komplexitätsklassen
- NPC Beweise
- Die große Frage der Informatiker P=NP oder PNP?
- 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
- 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
- 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