GThi Musterklausur 27.01.2009

Musterklausur

Grundlagen der theoretischen Informatik

Studiengang Informatik und Medieninformatik

Aufgabe 1

Geben Sie eine Turingmaschine $ \mathcal{A} $ an, die die Funktion $ f : \mathbb{N} \to \mathbb{N}, n \mapsto (2*n)+1 $ berechnet. Erläutern Sie die Arbeitsweise von $ \mathcal{A} $.

Hinweis: Für $ n \in \mathbb{N} $ gilt: $ n $ wird dargestellt als $ a^n, a \in \Sigma $.

Aufgabe 2

Gegeben sei die Chomsky-Grammatik

$ G = \left( V, \Sigma, P, S \right) $ mit

$ V = \left\{ S, B \right\} $

$ \Sigma = \left\{ a, b, c \right\} $

$ P = \left\{ S \to aSBc, S \to abc, cB \to B, cB \to Bc, bB \to bb \right\} $

a) Von welchem maximalen Typ ist $ G $? Begründen sie Ihre Antwort.

b) Bestimmen Sie drei Wörter $ w $ der Sprache $ L(G) $. Begründen Sie Ihre Antwort.

c) Gilt $ \varepsilon \in L(G) $? Begründen Sie Ihre Antwort.

d) Beschreiben Sie die durch $ G $ erzeugte Sprache $ L(G) $.

e) Ist der maximale Typ von $ L(G) $ kleiner als der von Ihnen in a) angegebene maximale Typ von $ G $? Begründen Sie Ihre Antwort.

Aufgabe 3

Beweisen oder widerlegen Sie folgende Aussagen. Begründen Sie Ihre Antworten - dabei dürfen Sie den gesamten Stoff und alle Resultate der Vorlesung verwenden.

a) Jedes Problem ist entscheidbar.

b) $ R $ ist entscheidbar gdw. $ R $ und $ \overline{R} $ partiell entscheidbar sind.

c) Es ist $ L $ eine Sprache. Wenn es eine natürliche Zahl $ n_0 \ge 1 $ gibt, so daß gilt: jedes Wort $ w \in L $ mit $ |w| \ge n_0 $ läßt sich zerlegen in $ w = xyz $ mit $ y \ne \varepsilon, xy^kz \in L $ für alle $ k \ge 0 $, dann ist L regulär.

d) Die Ackermannfunktion ist LOOP-berechenbar, aber nicht WHILE-berechenbar.

e) Jede Typ-0-Sprache ist entscheidbar.

f) Wenn $ L $ eine Typ-2 Sprache ist und $ L = L_1 \cup L_2 $, dann sind $ L_1 $ und $ L_2 $ auch Typ-2 Sprachen.

g) Typ-3-Sprachen sind abgeschlossen unter $ \cup $, $ \cap $ und Komplement.

h) Typ-2-Sprachen sind abgeschlossen unter $ \cup $, $ \cap $ und Komplement.

Aufgabe 4

Geben Sie eine kontextfreie Grammatik $ G $ für die folgende Sprache der Wörter über $ \left\{ a, b, c \right\} $ an: $ L = \left\{ a^i b^j c^k \mid i = j \vee j = k \wedge i, j, k \ge 1 \right\} $. Begründen Sie Ihre Antwort.

Aufgabe 5

Geben Sie ein LOOP-Programm an, das die Funktion

$ f : \mathbb{N}^2 \to \mathbb{N}, (x, y) \mapsto \begin{cases} x+y, & falls x \le y \\ x-y, & sonst \end{cases} $

berechnet und erklären Sie seine Arbeitsweise. Verwenden Sie dabei nur jene Wertzuweisungen, die in der Vorlesung in der Definition der Syntax von LOOP-Programmen definiert wurden - also keine weiteren Abkürzungen.

Aufgabe 6

Der DEA $ \mathcal{A} $ sei wie folgt gegeben:

[Im Original liegt der DEA als Zeichnung vor]

$ \mathcal{A} = \left( \left\{ q_0, q_1, q_2, q_3, q_4, q_5 \right\}, \left\{ a, b \right\}, q_0, \Delta, \left\{ q_1 \right\} \right) $

$ \Delta = \left\{ (q_0, a, q_1), (q_0, b, q_4), (q_1, a, q_3), (q_1, b, q_2), (q_2, a, q_1), (q_2, b, q_4), (q_3, a, q_1), (q_3, b, q_4), (q_4, a, q_5), (q_4, b, q_4), (q_5, a, q_5), (q_5, b, q_2) \right\} $

Geben Sie den zu $ \mathcal{A} $ reduzierten DEA $ \mathcal{A}_{red} $ an.

Aufgabe 7

Beim Hitting Set Problem ist eine Kollektion $ C = \left\{ C_1, \ldots, C_m \right\} $ von Teilmengen einer Grundmenge $ S \left( C_i \subseteq S, 1 \le i \le m \right) $ und eine positive ganze Zahl $ k \le |S| $ gegeben. Gefragt ist, ob es eine Menge $ S' \subseteq S $ gibt mit $ |S'| \le k $, so daß $ S' $ von jeder Teilmenge $ C_i $ mindestens ein Element enthält (d.h. $ S' \cap C_i \ne \emptyset $ für alle $ i, 1 \le i \le m $).

a) Geben Sie an, ob das Problem in NP ist. Begründen Sie ihre Antwort.

b) Wann ist Problem NP-hart?

c) Welche Methode kennen Sie prinzipiell, um zu zeigen, daß ein Problem NP-hart ist?

Aufgabe 8

Gegeben sei folgender NEA $ \mathcal{A} $

[Im Original liegt der NEA als Zeichnung vor]

$ \mathcal{A} = \left( \left\{ q_0, q_1, q_2 \right\}, \left\{ a, b \right\}, q_0, \Delta, \left\{ q_2 \right\} \right) $

$ \Delta = \left\{ (q_0, a, q_0), (q_0, b, q_2), (q_1, a, q_0), (q_1, b, q_1), (q_2, a, q_1), (q_2, b, q_0) \right\} $

Verwenden Sie das Lemma von Arden, um zu $ \mathcal{A} $ einen regulären Ausdruck $ \alpha $ anzugeben mit $ L(\mathcal{A}) = L(\alpha) $. Erläutern Sie Ihre Vorgehensweise.

Aufgabe 9

Für das Alphabet $ \Sigma = \left\{ a, b \right\} $ und $ L \subseteq \Sigma^* $ sei

$ equal(L) := \left\{ w \in \Sigma^* \mid w \in L \wedge |w|_a = |w|_b \right\} $.

Beweisen oder widerlegen Sie:

a) Ist $ L $ regulär, so auch $ equal(L) $. a) Ist $ L $ entscheidbar, so auch $ equal(L) $.