Gthi Klausur 21.02.2007

Aufgabe 1 Grammatiken

// Genauen Grammatiken kenn ich nicht mehr, es waren 2 gegeben und man musste die Aufgabe war genauso wie folgende, welche ich aus einer Übung entnommen habe

Aufgabe 2 Theoriefragen: wahr oder nicht wahr? (10 Punkte)

• a) Die Ackermann-Funktion wächst schneller als jede LOOP-berechenbare Funktion.
• b)
• c)
• d) UNIV ist in $ \mathcal{L}_0 $.
• e)
• f) Wenn $ L_1 $ und $ L_2 $ regulär sind, dann ist $ (L_1\cup L_2)\cdot(L_1\cap L_2)^* $ (zumindest so ungefähr) auch regulär.
• g)
• h)
• i) Die Erfüllbarkeit aussagenlogischer Formeln ist entscheidbar.
• j) Das Komplement einer rekursiven Menge ist rekursiv.

//die genaue Anordnung fällt mir nicht ein, ist auch egal

Aufgabe 3 CYK

//könnte auch eine andere Aufgabe gewesen sein

$ G=(\{S,A,B,C\},\{a,b,c\},\{S\rightarrow AB,A\rightarrow a,B\rightarrow b,C\rightarrow c,D\rightarrow AC,\ldots ?\},S) $

Gegeben war eine Grammatik, diese war kontextfrei und enthielt ein unerreichbares Nichtterminalsymbol.

a) Ist die Grammatik in CNF? Begründung angeben

b) Bestimmen Sie mit dem CYK-Algorithmus, ob $ w = abac \in L(G_1) $ ist. Formen Sie dazu, falls nötig, die Grammatik in CNF um und entfernen sie vorher unerreichbare sowie nichtterminierende Symbole.

Aufgabe 4 WHILE

a) Geben Sie ein WHILE-Programm an, mit dem man ein LOOP-Konstrukt simulieren kann. Verwenden Sie dazu die neue Variable y.

b) Geben sie ein WHILE Programm an, das die Funktion $ f:\mathbb{N}^2\rightarrow\mathbb{N}:(x_1,x_2)\mapsto\operatorname{kgV}(x_1,x_2) $ berechnet. Sie dürfen dabei folgende WHILE Programme benutzen: $ min,max,mult,div,\dot{-},+ $ (z.B. $ x_1:=mult(x_1,x_2) $)

c) Ist $ f $ µ-rekursiv? Begründen sie kurz.

Aufgabe 5 Kellerautomat

// könnte auch eine andere Aufgabe gewesen sein

a) Geben die einen Kellerautomaten $ A $ an, der mit leerem Keller akzeptiert, sodass:

$ L(A) = \{ w | w \in \{a,b,c\}^*\ \mathrm{und}\ |w_a| = |w_c|\} $

b) Welche weitere Akzeptanzbedingung für Kellerautomaten kennen Sie aus der Vorlesung?

c) Welche Sprachklasse wird von Kellerautomaten akzeptiert?

Aufgabe 6 DEA

// es war ein DEA $ \mathcal{A} $ gegeben

a) Entscheiden sie welche der drei Aussagen $ L(\mathcal{A}) $ beschreiben.

• die Wörter haben immer eine gerade Anzahl a´s oder b´s
• es sind immer gleich viele a´s und b´s in einem Wort
• die Wörter enden mit dem gleichen Buchstaben, mit dem sie begonnen haben

b) Geben sie das Arden-Lemma an und wenden sie es auf den DEA $ \mathcal{A} $ an, um einen regulären Ausdruck anzugeben.

c) Geben sie eine Typ-3-Grammatik G an, für die $ L(\mathcal{A})=L(G) $ gilt! Begründen Sie, warum ihre Grammatik vom Typ 3 ist!

Aufgabe 7 PKP

//könnte auch eine andere Aufgabe gewesen sein

Geben sie für folgende PKP´s eine Lösung an, wenn sie eine haben und begründen sie, wenn das PKP keine Lösung hat.

• a) $ (a,aba),(b,bab),(abab,ab) $
  
• b) $ (ba,bab),(bba,abb),(bab,abb) $ (ist jetzt geraten aber nach dem Schema)

Aufgabe 8 NP,NP-hart

Gegeben: zwei Graphen $ (V1,E1) $ und $ (V2,E2) $ und eine Zahl $ k $. Das Problem Prob: Gibt es $ V_1' \subseteq V_1 $ und $ V_2' \subseteq V_2 $ mit $ |V_1'|=|V_2'|=k $, sodass für alle $ v,u \in V_1' $, $ v',u' \in V_2' $ mit $ f(v)=v' $ und $ f(u)=u' $ folgendes gilt: $ (u,v) \in E_1 $ gdw. $ (u',v') \in E_2 $.

a) Ist $ Prob \in NP $? Begründen Sie!

b) Ist Prob NP-hart? Zeigen Sie das ggf. indem Sie das aus der Vorlesung bekannte Problem Clique darauf zurückführen!

Aufgabe 9 Abschlusseigenschaften

Gegeben sind zwei Sprachen $ L_1 = \{a^nb^na^mb^m | n,m \geq 0\} $ und $ L_2 = \{a^xb^y | x,y \geq 0\} $. Beweisen oder widerlegen sie die Aussagen

a) $ L_1 \cap L_2 $ ist kontextsensitiv

b) $ L_1 \cdot L_2 $ ist nicht entscheidbar