Reguläre Sprache, endlicher Automat
Äquivalenz von NEA’s und DEA’s
Entfernen von ε-Übergängen
Satz von Kleene
Satz von Nerode
Die Church’sche These
Halteproblem ist nicht entscheidbar
Die universelle Sprache Lu ist nicht entscheidbar, aber semi entscheidbar
Schwierigkeit von Entscheidungs- und Optimierungsproblem
Der Satz von Cook (Steven Cook, 1971)
Nicht-Existenz eines FPTAS
Eigenschaften kontextfreier Sprachen
ndet. KA kontextfreie Sprachen
Zuletzt geändertvor 2 Jahren
