ε–Abschluss
Pumping-Lemma für reguläre Sprachen
Überflüssig
Zustandsäquivalenz
Der Äquivalenzklassenautomat
Zeugen für Nichtäquivalenz
Verallgemeinertes Pumping-Lemma
Rechtsinvarianz und Index
Nerode-Relation
berechenbar / totalrekursiv
Die universelle Turing-Maschine
Die Gödelnummer
Die Diagonalsprache
Halteproblem
Trennzeichen #
Die Universelle Sprache
Eigenschaften von (semi-)entscheidbaren Sprachen
Problem, Kodierungsschema
NP-Vollständigkeit für Sprachen
NP-Vollständigkeit für Entscheidungsprobleme
Transitivität der poly. Transformation
Die Klassen co-P und co-N P
Aufzählungsprobleme
Pseudopolynomiale Algorithmen
Starke N P-Vollständigkeit
Approximationsalgorithmen
Absolute/Relative Approximationsalgorithmen
Genereller Ansatz
Bestmögliche Approximationsgüte
Approximationsschemata
DTAPE(s(n))
NTAPE(s(n))
Links/Rechtsableitung, Eindeutigkeit
Chomsky-Normalform
Der CYK-Algorithmus
Das Pumping-Lemma für kontextfreie Sprachen
Ogden’s Lemma für kontextfreie Sprachen
Nutzlose Variablen
Kellerautomaten
Sprache der korrekten Rechenwege
Zuletzt geändertvor 2 Jahren
