Vordiplomsklausur Theoretische Informatik (InfoIII) vom
18.4.2001 ungefaehre Fragestellungen.
Fragen:
- Frage 1 (3pkte)
Geg:
Eine Sprache ueber dem Alphabet Sigma{a,b}
fuer die gilt: es kommt ueberhaupt kein a vor oder genau zwei.
Ges:
Geben Sie einen DFA an. (2pkte)
Geben Sie den regulaeren Ausdruck an. (1pkt)
- Frage 2 (3pkte)
Geben Sie das Pumpinglemma fuer regulaere Sprachen an (1pkt)
Beweisen Sie dass
L={a^(n^2) | n e N und Alphabet Sigma{a}} (~2pkte)
- Frage 3 (4pkte)
Geg. ist folgende Grammatik in Chomsky-Normalform:
S -> BA | BS | a
A -> BA | AS | a
B -> SA | BC | b
C -> c
a) Gesucht ist mit dem CYK Algorithmus, ob w kontextfrei ist.
Tragen Sie die Zwischenschritte in einer
Dreiecks-Tabelle ein (2pkte)
b) Ist w = abca nun in der Sprache ? (1pkt)
c) Wie gross ist die Komplexitaet des Algorithmus? (1pkt)
- Frage 4 (2pkte)
Bauen Sie eine Registermaschinenprogramm welches aus
x,y,0,0,0.....
x,y,2*x+y,0... berechnet. (2pkte)
- Frage 5 (3pkte)
Geben Sie die Definition von P(primitiv-rekursiv) an. (1pkt)
Zeigen Sie dass f(x) = 3^x primitiv-rekursiv ist. (2pkte)
- Frage 6 (5pkte)
Geg. L3, L2, L1, L, L0
Ges: Welcher Zusammenhang besteht zwischen diesen
Sprachgruppen?
Geben Sie jeweils ein Beispiel an. (5pkte)
- Frage 7 (4pkte)
a)Wie ist Abzaehlbarkeit definiert? (1pkt)
b)Wie ist Entscheidbarkeit definiert? (1pkt)
c)In was fuer einer Beziehung stehen Abzaehlbarkeit
und Entscheidbarkeit? (1pkt)
d)Geben Sie ein Beispiel an welches nicht entscheidbar,
aber abzaehlbar ist. (1pkt)
- Frage 8 (2pkte)
Geben Sie ein Beispiel an welches in NP liegt. (1pkt)
Was ist NP-vollstaendig? (1pkt)
(Verbesserte Version vom 4. Mai 2001)
|
