Gthi Klausur 15.02.2005

Aufgabe 1 (10 Punkte)

Sprache L gegeben mittels Grammatik G
($ P = \{S \rightarrow AT, A \rightarrow a, B \rightarrow b, C \rightarrow c, ? \rightarrow AW, X \rightarrow ? \} $)
Grammatik G in Chomsky-Normalform

a) Pruefen Sie mit CYK-Algorithmus, ob w = aaabcaca Element der Sprache L ist.
b) Warum kann man hier den CYK-Algorithmus verwenden?

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

a) $ L = \{a^nb^nc^n | n \ge 0\} $ L ist entscheidbar und regulaer.
b) $ L = \{a^nb^n | n \ge 0\} $ Wenn L entscheidbar, dann auch rekursiv aufzaehlbar.
c) Das Komplement des Halteproblems ist rekursiv aufzählbar.
d) Der Durchschnitt zweier kontextfreier Sprache ist regulär.
e) Das Komplement von UNIV ist entscheidbar.
f) Jede Sprache über einem einelementigen Alphabet ist erkennbar.
g) Ackermann ist total und deswegen Loop-berechenbar.
h) Das Problem 'TM1 verhält sich bei leerer Eingabe wie TM2' ist entscheidbar.
i) Typ-3-Sprachen sind unter Schnitt, Vereinigung und Komplement abgeschlossen.
j) Es sei L eine regulaere Sprache. Dann gibt es eine natuerliche Zahl n, so dass gilt: Jedes Wort w Element L mit |w| < n laesst sich zerlegen in w=xyz mit [...] ("Pumping-Lemma")

Aufgabe 3 (primitiv-rekursiv und μ-rekursiv) (10 Punkte)

a) Zeigen Sie, dass $ \mathbb{N} \rightarrow \mathbb{N}, x \mapsto 2^x $ primitiv-rekursiv ist.
b) Zeigen Sie, dass $ \mathbb{N} \rightarrow \mathbb{N}, x \mapsto \left\lceil \sqrt{x}\ \right\rceil $ $ \mu $-rekursiv ist.

Aufgabe 4 (Kellerautomat, Sprachen) (12 Punkte)

gegeben Sprache $ L = \{(a^nba^n)^i | n \ge 1, i \ge 0\} $

a) Geben Sie Kellerautomaten, der L mit leerem Keller akzeptiert, an.
b) Geben Sie eine Grammatik G mit L(G) = L an.
c) Welchen Typ hat Ihre angegebene Grammatik?

Aufgabe 5 (regulaerer Ausdruck) (10 Punkte)

gegeben: DEA A mit 5 Zustaenden
(im Original als Zeichnung gegeben, hier durch Uebergangsfunktion) $ A = \{Q, \Sigma, q_0, \delta, F\}\; $
$ Q = \{q_0, q_1, q_2, q_3, q_4\}\; $
$ \Sigma = \{a, b\}\; $
$ \delta = \{ (q_0, a, q_3), (q_0, b, q_4), (q_1, a, q_0), (q_1, b, q_1), (q_2, a, q_2), (q_2, b, q_0), (q_3, a, q_0), (q_3, b, q_1), (q_4, a, q_2), (q_4, b, q_0) \}\; $
$ F = \{q_3, q_4\}\; $

Aufgabe: Geben Sie einen regulaeren Ausruck $ \alpha\; $ an mit $ L(A)= L(\alpha)\; $ und erklaeren Sie ihre Schritte.

Aufgabe 6 (Loop)(10 Punkte)

a) Geben Sie ein Loop-Programm fuer folgende Funktion an:

$ f: \mathbb{N}^2 \rightarrow \mathbb{N}, (x,y)=\begin{cases} 0, & \mbox{falls } x=y \mbox{ } \\ 1, & \mbox{falls }x>y\mbox{ } \\ 2, & \mbox{sonst } \end{cases} $

b) Ist dieses Programm auch primitiv-rekursiv? Begruenden Sie kurz.

Aufgabe 7 (PKP)(10 Punkte)

a) Haben folgende Instanzen des PKP eine Loesung? Geben Sie ggf . eine Loesung an.

PK1: (bb, bba), (?, ?), (?, ?); Loesung: 1, 2, 1, 3
PK2: (bb, b), (b, aa), (b, a); keine Loesung

b) Welches Problem wurde in der Vorlesung auf das PKP reduziert?

Aufgabe 8 (NP)(10 Punkte)

Problem-Beschreibung von UIP:
Gegeben sind zwei ungerichtete Graphen G_1 und G_2. Gibt es einen Untergaphen von G_2, der zu G1 isomorph ist?
Def. Isomorph: wenn es eine bijektive Abbildung gibt mit [...]

a) Liegt UIP in NP? Begruenden Sie.
b) Zeigen Sie durch Reduktion des aus der Vorlesung bekannten Problems Clique auf UIP, dass UIP NP-hart ist.

Aufgabe 9 (10 Punkte)

$ \Sigma=\{a,b\}, L \subseteq \Sigma^* $
$ even(L) = \{w \in \Sigma^* | w \in L \and \left|w\right|\ ist\ gerade\} $

Begruenden oder wiederlegen Sie mit Begruendung:
a) Wenn L regulaer, dann auch even(L) regulaer.
b) Wenn L unendlich, dann auch even(L) unendlich.

Lösungen

Aufgabe 2

a) falsch, Widerlegbar mit Pumping Lemma

b) wahr, da L durch Typ-1 Grammatik erzeugbar ist, zweiter Teil der Aussage ist Satz 13.4

d) falsch

Aufgabe 3

a)

$ f(0)=g()=1 $
$ f(y+1)=h(f(y),y)=mult(2,f(y)) $

Andere Möglichkeit wäre ein Loop-Programm zu schreiben:

$ x_0 $:= 1;
$ x_3 $:= 1;
LOOP $ x_1 $ DO (

  $ x_2 $ := 0

  LOOP $ x_0 $ DO $ x_0 $:= $ x_0 $ + 1; END;

) END;

LOOP $ x_3 $ DO $ x_0 $:= 1; END;

Andere primitive Rekursion:

$ f(0) = 1 $
$ f(x+1) = add(f(x),f(x)) $

b) $ f(x)=\mu(\dot{-}(x, mult(y,y))\qquad (=min\{y|x \dot{-} y^2=0\}) $

Aufgabe 4

a)

$ \begin{matrix} A =(Q,\Sigma,\Gamma,q_0,Z_0,\Delta)\\ Q = \{q_0,q_1,q_2,stop\}\\ \Sigma = \{a,b\}\\ \Gamma = \{Z_0,Z\}\\ \begin{matrix} \Delta = \{ & (q_0,\epsilon,Z_0,\epsilon,stop),\\ & (q_0,a,Z_0,ZZ_0,q_1),\\ & (q_1,a,Z,ZZ,q_1),\\ & (q_1,b,Z,Z,q_2),\\ & (q_2,a,Z,\epsilon,q_2),\\ & (q_2,a,Z_0,ZZ_0,q_1),\\ & (q_2,\epsilon,Z_0,\epsilon,stop)\}\\ \end{matrix}\\ \end{matrix} $

b)

$ \begin{matrix} G=(N,\Sigma,P,S)\\ N = \{S,A\}\\ \Sigma = \{a,b\}\\ \begin{matrix} P : & S \rightarrow \epsilon\\ & S \rightarrow aAaS\\ & S \rightarrow aAa\\ & A \rightarrow aAa\\ & A \rightarrow b\\ \end{matrix}\\ \end{matrix} $

c)

G ist vom Typ-2 und nicht vom Typ-3, da G nicht rechtslinear.

Aufgabe 5

Loesung (per Lemma von Arden): $ \alpha = (aa + abb^*a + bb + baa^*b)^*(a + b)\; $

Aufgabe 6

a)

LOOP x1 DO(          // 1)
    x3 := 1;
    LOOP x2 DO(
        x3 := 0;
    )END;
    x2 := x2 - 1;    //modifizierte Differenz
)END;
x0 := x2;           // 2)
LOOP x0 DO(         // 3)
    x0 := 2;
)END;
LOOP x3 DO(         // 4)
    x0 := 1;
)END;

Was mach dieses Programm?

1. Es subtrahiert x2 von x1 (in Einerschritten). Wenn x2 bereits während des Subtrahierens 0 wird, dann bleibt der Merker x3 = 1. Wenn x1 - x2 tatsächlich genau 0 ist oder x1 - x2 > 0 ist, dann ist der Merker x3 = 0 und somit ohne Bedeutung.
2. Der Wert von x2 wird auf x0 übergeben.
3. Wenn x0 größer 0 ist wird x0 auf 2 gesetzt. (x > y)
4. Wenn x3 größer 0 ist wird x0 auf 1 gesetzt. (x < y)
5. Wenn sowohl x0 als auch x3 gleich 0 sind, dann bleibt x0 = 0. (x = y)

b)

Die Klasse der LOOP-berechenbaren Funktionen stimmt mit der Klasse der primitiv-rekursiven Funktionen überein.

Aufgabe 7

b)

Das MPKP (modifiziertes Postsches Korrespondenzproblem) kann auf das PKP reduziert werden.

Aufgabe 9

a) Falsch

2 Fälle n und m gerade oder n und m ungerade.

Diese zwei Fälle sind Teil von L = { a^n b^m | n>= 0, m >=0 }.

Es wurde in der Vorlesung mittels PL geprüft, dass L nicht regulär ist.

($ a^n b^m $nur dann nicht regulär, wenn gefordert ist $ m!=n $)

b) Falsch

L = {a^n | n ist ungerade }

L ist unendlich, da es unendlich viele ungerade Zahlen gibt.

Even(L) ist leer und damit nicht unendlich.