Prüfungsfragen "Theoretische Informatik" bei Franz Kummert

(die Fragen sind noch nicht geordnet und teilw. inhaltlich doppelt. Stand ist 25.08.2003)

Was ist eine formale Grammatik, Aufbau, Tupel angeben, Elemente erklären, welche Einschränkungen erf. die anderen Teilklassen der Chomsky-Hierarchie
nenne Sprache, die kfr. aber nicht reg. ist (z.B. a^{i b}i a^{i b a}i) => Beweis (Pumping Lemma)
Was ist TM, Konfigurationen. Warum sind kss. Sprachen entscheidbar, Längenmonotonie
formale Sprachen, allg. Regelgrammatik, Aufbau, Regeln (formal)
Aufzählung der den Grammatiken entspr. Automaten
TM: allg. Angabe einer Sprache, die akz. wird, die Start- in Endkonfiguration überführt. Wann liegt Endkonf. vor?
Welche Sprachkl. der Chomsky-Hierarchie sind entscheidbar (warum? -> expansiv)
Entscheidbarkeit, Halteproblem+Beweisskizze, dass kein Programm ex. das das HP löst, also angibt, ob P terminiert
Chomsky-Hierarchie (Was versteht man darunter? Unterschiede der Sprachklassen.)
Was ist Theoretische Informatik?
Pumping Lemma, EA, TM, KSS
Automaten
EA: Def., Start- und Endkonfiguration
Entscheidbarkeit (besonders kss)
Wann ist Wort Elem. einer Sprache?
Warum entspr. kfr. und reg. Sprachen sich nicht?
Welche Automaten entspr. den Sprachklassen. wann akz. sie ein Wort (am Bsp. EA, NEA, bzw. TM)
Was heißt Akzeption bei den Automaten