uni/til/ue1/til-ue1.md

% Theoretische Informatik und Logik ue1 % 21 Oktober 2020

Aufgabe 1.1

Wir definieren in einem initialen Versuch eine Turingmachine $M$ wie folgt:

$$ M = ({ q_i \mid 0 \leq i \leq 2 }, { \underbar[, \underbar], \underbar(, \underbar) }, { \underbar[, \underbar], \underbar(, \underbar), P, B }, \delta, q_0, B, { q_2 }) $$

wobei $\delta$ gegeben ist durch:

$\delta$	$\underbar[$	$\underbar($	$\underbar]$	$\underbar)$	P	B
$q_0$	$(q_0, \underbar[, R)$	$(q_0, \underbar (, R)$	$(q_1, P, L)$	$(q_1, P, L)$	$(q_0, P, R)$	$(q_2, B, S)$
$q_1$	$(q_0, P, R)$	$(q_0, P, R)$	$(q_1, \underbar], L)$	$(q_1, \underbar), L)$	$(q_1, P, L)$
$q_2$

Erklärung

Die Idee hinter dieser Turingmaschine ist es, die erste rechte Klammer zu finden. Nach jeder rechten Klammer folgt eine Suche nach der nächsten linken Klammer. Auf diese Art und Weise können immer verlässlich zwei zugehörige Klammern aufeinanderfolgend prozessiert werden, angenommen die Klammerung ist richtig. Das Symbol $P$ bezeichnet an dieser Stelle ein bereits erfolgreich prozessiertes Eingabesymbol. Versuchen wir nämlich gleich mit linken Klammern anzufangen, stößen wir an das Problem, dass wir nicht wissen, wann die dazugehörige rechte Klammer auf uns zukommt.

Ein typischer Ablauf für die wohlgeformte Beispieleingabe []([]) wäre dann:

$$ \begin{aligned} &Bq_0[][([])]B &&\Rightarrow B[q_0][([])] &&\Rightarrow Bq_1[P[([])]B &&\Rightarrow BPq_0P[([])]B \ \Rightarrow &BPPq_0[([])]B &&\Rightarrow ... &&\Rightarrow BPP[([p_0])]B &&\Rightarrow BPP[(q_1[P)]B \ \Rightarrow &BPP[(Pq_0P)]B &&\Rightarrow BPP[(PPq_0)]B &&\Rightarrow BPP[(Pp_1PP]B &&\Rightarrow ... \ \Rightarrow &BPP[q_1(PPP]B &&\Rightarrow BPP[Pq_0PPP]B &&\Rightarrow ... &&\Rightarrow BPP[PPPPq_0]B \ \Rightarrow &BPPq_1[PPPPPB &&\Rightarrow BPPPq_0PPPPPB &&\Rightarrow ... &&\Rightarrow BPPPPPPPPq_2B \ \end{aligned} $$

Wir notieren dass das Leerwort $\varepsilon$ zugelassen ist, weil aus Zustand $q_0$ direkt in den Endzustand $q_3$ übergegangen werden kann, wenn ein Blank Symbol $B$ gelesen wird.

Ein Problem wären Eingaben in denen die Klammern "wohlgeformt" erscheinen, aber in der falschen Reihenfolge auftreten, wie etwa [(]). Aber die Turing Maschine ließe sich leicht erweitern, nämlich muss der Zustand $q_1$ aufgespalten werden auf zwei separate Zustände, die jeweils für die Suche der zugehörigen Klammerart zuständig sind. Dann ließe sich beispielsweise auch einbauen, dass die Maschine halten soll, wenn nach einer rechten ] Klammer eine linke ( Klammer folgt.

Weiters müssen wir Fälle behandeln, in denen es zu viele führende öffnende Klammern gibt, beispielsweise (() oder [(). Um das Problem zu lösen führen wir einen Zwischenschritt vor Erreichen des Endzustandes wird. In diesem Zwischenschritt lesen wir über alle $P$ Symbole nach links, bis wir hoffentlich auf ein $B$ Symbol stoßen. Falls nicht, handelt es sich um kein gültiges Wort.

Ergänzung

die korrekte Turingmaschine:

$$ M = ({ q_i \mid 0 \leq i \leq 4 }, { \underbar[, \underbar], \underbar(, \underbar) }, { \underbar[, \underbar], \underbar(, \underbar), P, B }, \delta, q_0, B, { q_4 }) $$

$\delta$	$\underbar[$	$\underbar($	$\underbar]$	$\underbar)$	P	B
$q_0$	$(q_0, \underbar[, R)$	$(q_0, \underbar (, R)$	$(q_1, P, L)$	$(q_2, P, L)$	$(q_0, P, R)$	$(q_3, B, L)$
$q_1$	$(q_0, P, R)$		$(q_1, \underbar], L)$	$(q_1, \underbar), L)$	$(q_1, P, L)$
$q_2$		$(q_0, P, R)$	$(q_2, \underbar], L)$	$(q_2, \underbar), L)$	$(q_2, P, L)$
$q_3$					$(q_3, P, L)$	$(q_4, B, S)$
$q_4$

Aufgabe 1.2

(a)

(1)

Für $K_1$ stellt $(3,2,1,1)$ eine Lösung dar.

|0 1|0 1|1 0 0|1 0 0|
|0 1 0 1 1|0 0 1|0|0|
 3       2    1 1

(2)

Für $K_2$ stellt $(3,4,2,1,4)$ eine Lösung dar.

|0 0 0|1 0 0 1|0 1|0 1|1 0 0 1|
|0|0 0 1|0 0 1|0 1 0 1 1|0 0 1|
 3 4     2     1          4

(3)

Für $K_3$ kommt nur in Frage, jeweils mit $1$ oder $4$ zu beginnen, da sonst bereits die ersten Zeichen nicht korrespondieren.

Ein Start mit $4$ lässt sich leicht ausschließen, nämlich lässt sich in Folge auf eine $4$ nur eine weitere $4$ verwenden und die Längen der zwei Strings wachsen unterschiedlich schnell:

|1 1 1|1 1 1|..
|1|1|..
 4 4 ..

Bleibt also nur noch ein Start mit $1$. Hier können wir alle individuellen Zweige betrachten:

Bei den Folgen $(1,2,3)$ und $(1,2,5,2,3)$ stoßen wir an das Problem, das der untere Teil der Folge mit 000 nicht weiter oben vervollständigt werden kann:

|0 1|0 1|1 1|            |0 1|0 1|1 1 0 0|0 1|1 1|
|0 1 0 1 1|1 0|0 0| oder |0 1 0 1 1|1 0|0 0 1 1|1 0|0 0|
 1         2   3          1         2   5       2   3

Bei den Folgen $(1, 2, 5, 1, 6, 2, 6)$ und $(1, 1, 6, 2, 6)$ kann der untere Teil der Folge mit 00 nicht vervollständigt werden:

|0 1|0 1|1 1 0 0|0 1|1 0 1|0 1|1 0 1|
|0 1 0 1 1|1 0|0 0 1 1|0 1 0 1 1|0|1 0|0|
 1         2   5       1         6 2   6

oder

|0 1|0 1|1 0 1|0 1|1 0 1|
|0 1 0 1 1|0 1 0 1 1|0|1 0|0|
 1         1         6 2   6

Bei der Folge $(1, 1, 6, 1)$ kann das untere 100 nicht vervollständigt werden:

|0 1|0 1|1 0 1|0 1|
|0 1 0 1 1|0 1 0 1 1|0|0 1 0 1 1|
 1         1         6 1

Und vielleicht der speziellste Fall, die Folge $(1, 2, 5, 2, 5)$ lässt sich nur auf eine Art vervollständigen die sich unendlich wiederholt (daher $(1, 2, 5, 2, 5, 2, 5, ...)$):

|0 1|0 1|1 1 0 0|0 1|1 1 0 0|..
|0 1 0 1 1|1 0|0 0 1 1|1 0|0 0 1 1|..
 1         2   5       2   5       ..

(4)

|0 1|0 1|1 0 1|0 1|1 0 1|0 0|1 1 1|
|0 1 0 1 1|0 1 0 1 1|0|1 0|0|1 1|1|
 2         2         5 1   5 3   6

Für $K_4$ stellt $(2,2,5,1,5,3,6)$ eine Lösung dar.

(b)

Behauptung

Das unäre PCP ist entscheidbar.

Beweis

Wenn ein Paar $(x, y)$ existiert wo $|x| = |y|$, dann gibt es klarerweise eine Anordnung. Vergleichsweise, wenn kein solches Paar existiert, daher $|x_i| < |y_i| \lor |x_i| > |y_i|, 0 \leq i \leq k$, kann es keine Anordnung geben. $\square$

Aufgabe 1.3

$$ \Sigma = {\underbar0, \underbar1} $$

(a)

Hier handelt es sich um eine nicht-triviale Eigenschaft, da es Turingmaschinen gibt, die eine rekursive Sprache oder eine rekursiv aufzählbare Sprache akzeptieren. Wäre für eine Turingmaschine $M$ die Sprache rekursiv, daher $L(M)$ rekursiv, so wäre auch das Komplement $\bar L(M)$ der Sprache rekursiv. Ist $L(M)$ jedoch nur rekursiv aufzählbar, so kann $\bar L(M)$ nicht rekursiv aufzählbar sein.

Beispiel

Sei $L = { w \mid w \in L(M) }$ rekursiv aufzählbar, dann ist $\bar L = { w \mid w \not \in L(M) }$ nicht rekursiv aufzählbar.

Jede reguläre Sprache aber ist rekursiv, beispielsweise $L = {0,1}^*$. Für jede reguläre Sprache ist auch ihr Komplement rekursiv. Rekursive Sprachen sind eine wahre Teilmenge aller rekursiv aufzählbarer Sprachen. Die Eigenschaft ist nach dem Satz von Rice daher nicht trivial und in Folge unentscheidbar.

(b)

Es lässt sich eine Turingmaschine $M$ konstruieren, welche die Anzahl an Symbolen der Codierung einer Turingmaschine $T$ auf eine Länge von 1000 überprüft. Das Problem ist somit entscheidbar. Das ist keine Eigenschaft der Sprache, sondern der Turingmaschine.

(c)

Ja, per Definition muss $L$ in $\mathcal{P}(\Sigma ^*)$ enthalten sein.

(d)

Wir können zur Lösung dieses Problems eine Universal Turing Maschine $T$ nehmen, welche die Codierung einer Turing Maschine $M$ nimmt um sie mit dem leeren Band zu simulieren. $T$ hält nach höchstens 101 Schritten, weil entweder $M$ früher hält oder von $T$ aufgehalten wird. Somit ist das Problem entscheidbar.

(e)

Es gibt Sprachen, die keine Palindrome enthalten, aber auch welche, die welche enthalten. Beispielsweise $L_1 = {0^n 1^n \mid n \geq 0 }$ und $L_2 = {0^n 1 0^n \mid n \geq 0}$. Diese Eigenschaft ist somit nicht trivial und nach dem Satz von Rice unentscheidbar.

(f)

Es gibt Sprachen die werden von Turing Maschinen akzeptiert, aber nicht von endlichen Automaten. Gleichzeitig gibt es andere Sprachen, die von beiden akzeptiert werden. Beiuspielsweise $L_1 = {0^n 1^n \mid n \geq 0 }$ und $L_2 = { 0, 1 }^*$. Diese Eigenschaft ist somit nicht trivial und nach dem Satz von Rice unentscheidbar.

Aufgabe 1.4

(a)

Nein.

Wählt man das Beispiel $L \cup \bar L = { a, b }^* = \Sigma$, so lassen sich ohne weitere Schwierigkeiten Beispiele bilden, für jene zwar $L$, aber nicht $\bar L$ rekursiv aufzählbar ist. Dies gilt beispielsweise für $L = \Sigma^ \setminus {a^n b^n \mid n \in \mathbb{N} }$.

(b)

Nein.

Hier können wir ein ähnliches Argument wie bei (a) betrachten, nämlich hat eine Sprache $L$ nur eine echte Obermenge, wenn sie eine echte Untermenge von $\Sigma^*$ ist. Jede solche Sprache $L$ ist dann ein Gegenbeispiel.

(c)

Ja.

Beispielsweise ist die leere Sprache ${}$ entscheidbar und diese ist eine Teilmenge jeder Sprache.

(d)

Nein.

Beispielsweise ist $\Sigma^*$ entscheidbar, aber nicht jede beliebige Teilmenge davon.

(e)

Nein.

Ist $A$ auf $B$ reduzierbar und $B$ rekursiv aufzählbar, so ist auch $A$ rekursiv aufzählbar. Im Allgemeinen können wir aber keine Aussage treffen, ob deswegen auch das Komplement $\bar A$ rekursiv aufzählbar ist.

(f)

Ja.

Ist $A$ auf $B$ reduzierbar und $B$ entscheidbar, so ist auch $A$ entscheidbar. Ist $A$ entscheidbar, so ist auch das Komplement $\bar A$ entscheidbar.

(g)

Ja.

Ist nämlich das PCP rekursiv entscheidbar, so sind auch die Sprachen, welche wir auf das PCP reduzieren rekursiv entscheidbar. Sind dann also $A$ und $\bar A$ rekursiv aufzählbar, so ist $A$ auch rekursiv und somit entscheidbar.

Aufgabe 1.5

(a)

$$ L_1 = { \underbar a^n \underbar b^{n \operatorname{mod} 3} \mid n \geq 0 } $$

$$ L_2 = { \underbar 0^n \underbar 1^m \mid n > m } $$

$L_1$ ist regulär, aber das müssen wir nicht einmal zeigen, da wir beweisen können, dass $L_2$ das nicht ist. Ist Nämlich einer der Sprachen $L_1$ und $L_2$ nicht regulär, so kann auch $L_1 \cup L_2$ nicht regulär sein. Dem Pumping Lemma zufolge können wir ein Wort aufteilen:

$$ w = xyz\ \ \ \ \text{mit } \lvert xy \rvert \leq o \text{ und } \lvert y \rvert > 0 $$

und es müsste gelten:

$$ w_i = xy^iz \in L\ \ \ \ \text{ für alle } i \geq 0 $$

wir können jetzt unser Wort abstrakt darstellen als:

$$ w = 0^m 0^{n-m} 1^m = xyz $$

sowie:

$$ w_i = 0^m (0^{n-m})^i 1^m = xy^iz $$

Betrachten wir nun aber Sonderfall $i = 0$ (mit $o = n$), so bekommen wir:

$$ xy^0z = 0^m 1^m $$

was nicht in der Sprache enthalten sein kann! Dem Pumping Lemma zufolge kann also $L_1 \cup L_2$ nicht regulär sein.

(b)

$$ L_{ADD} = { u \underline + v \underline = w \mid u,v,w \in { \underline 0, ..., \underline 9 }^* \land z(u) + z(v) = z(w) } $$

Wählen wir:

$$ w_i = xy^iz = 1 \underline + 1^i \underline = 2 $$

wobei $m = 2$, so sehen wir schnell dass $i = 1$ in Wahrheit ein Spezialfall ist, in denen das Wort $w_i$ Teil der Sprache $L$ ist. Versuchen wir nämlich $i = 2$, so stoßen wir auf ein Ergebnis das unmöglich Teil der Sprache $L$ sein kann:

$$ w_2 = 1 \underline + 11 \underline = 2 $$

Wörter der Sprache $L$ können daher nicht aufgepumpt werden und die Sprache ist dem Pumping Lemma zufolge keine reguläre Sprache.

(c)

$$ L = { y z y^r \mid y, z \in { \underline a, \underline b, \underline c }^* } $$

Da $y$ ein beliebiges Wort aus ${a,b,c}^$ sein darf, ist auch $y = \varepsilon$ zugelassen! Somit müssen wir um zu zeigen, dass $L$ regulär ist, lediglich einen Automaten konstruieren, der $y = \varepsilon \land z \in {a,b,c}^$ behandelt. Ein solcher Automat ist beispielsweise durch ^[abc]*$ (POSIX Extended Regex) gegeben.

Jedes Wort dass der endliche Automat akzeptiert ist ein Teil der Sprache $L$.

(d)

$$ L = { y y^r y \mid y \in { \underline a, \underline b, \underline c }^* } $$

Wählen wir:

$$ w_i = wv^iw = a^\frac{m}{2}a^{i\frac{m}{2}}a^\frac{m}{2} $$

so sind die Vorraussetzungen für das Pumping Lemma erfüllt. Betrachten wir nun $i = 0$, so merken wir, dass es leicht ist für $w_i$ nicht in der Sprache $L$ enthalten zu sein. $w = \underline a \underline a \underline a$ wäre bereits ein Gegenbeispiel, welches nicht aufgepumpt werden kann.