Answer to Question 1


Antwort:

a) Der Deterministische Endautomat (DEA) für die Sprache $L_3$ mit dem Wort $01$ als Eingabe kann wie folgt beschrieben werden:

1. Setze den Zustand $q_0$ als Startzustand.
2. Führe für jedes Zeichen $x$ des Eingabe-Wortes $01$ folgende Schritte aus:
   - Wenn der aktuelle Zustand $q$ und das eingelesene Zeichen $x$ der Eingabe-Sequenz entsprechen dem Paar $(q, x)$ in der folgenden Tabelle, gehe zum Zustand $q'$:

     | Zustand $q$ | Zeichen $x$ | Zustand $q'$ |
     |--------------|--------------|----------------|
     | $q_0$        | $0$          | $q_0$         |
     | $q_0$        | $1$          | $q_1$         |
     | $q_1$        | $0$          | $q_0$         |
     | $q_1$        | $1$          | $q_1$         |

   - Wenn kein solches Paar $(q, x)$ existiert, bleibe im aktuellen Zustand $q$.

3. Wenn das Eingabe-Wort $01$ vollständig gelesen wurde, ist der Zustand $q_1$ der Endzustand.

Der DEA erkennt die Menge der gültigen Suffixe $S_{01}(L_3)$ des Wortes $01$ in der Sprache $L_3$, da er nur die Suffixe akzeptiert, die mit dem Wort $01$ konkateniert eine Zeichenfolge in $L_3$ bilden.

b) Die leere Sprache $\emptyset$ ist die einzige Sprache, für die $S_\varepsilon(L) = \emptyset$. Alle anderen Sprachen enthalten mindestens das leere Wort $\varepsilon$ als Suffix.

c) Sei $L$ eine reguläre Sprache. Dann kann jede Menge der gültigen Suffixe $S_w(L)$ für jedes $w \in \Sigma^*$ ebenfalls regulär sein. Dies folgt aus dem Satz von Myhill-Nerode, der besagt, dass eine reguläre Sprache genau dann regulär ist, wenn ihr Myhill-Nerode-Automat endstatig ist. Da der Myhill-Nerode-Automat jedes Wort $w$ in eine endliche Zustandsmenge eindeutig abbildet, ist die Menge der gültigen Suffixe $S_w(L)$ endlich und kann daher regulär sein.

d) Die Sprache $L = \{a^nb^nc^n \mid n \in \N^+\}$ ist eine Beispielsprache für die Aussage gilt, dass es eine nichtreguläre Sprache $L$ gibt, bei der $S_w(L)$ für unendlich viele $w \in \Sigma^*$ regulär ist.

Die Sprache $L$ besteht aus allen Wörtern der Form $a^nb^nc^n$, wobei $n$ eine natürliche Zahl ist. Die Menge der gültigen Suffixe $S_w(L)$ für jedes $w \in \Sigma^*$ ist regulär, wenn $w$ aus der Form $a^nb^nc^n$ ist. Dann ist $S_w(L) = \{a^mb^mc^m \mid m \leq n\}$.

Die Sprache $L$ selbst ist jedoch nicht regulär, denn sie ist nicht finit definierbar. Es gibt kein endliches Automat, der diese Sprache erkennt.





****************************************************************************************
****************************************************************************************




Answer to Question 2


Antwort:

a) Der DEA $A'$ kann wie folgt definiert werden: $Q = \{Z_0, Z_1, Z_2, X\}$, $\delta(Z_i, a, X) = \{Z_j, X\}$ für alle $i, j \in \{0, 1, 2\}$ und $a \in \Sigma$. D.h., $A'$ liest jedes Symbol $a$ auf, überschreibt das aktuelle $X$ durch $a$ und geht in den nächsten Zustand $Z_j$.

b) Sei $w \in L(A)$, also gibt es eine Akzeptierungswelle $q_0, Z_0, a_1, q_1, Z_1, a_2, \dots, q_n, \epsilon$ für $A$. Da $A$ nur einen Zustand hat, folgt aus der Akzeptierungswelle $q_0, Z_0, a_1, q_0, Z_1, a_2, \dots, q_n, \epsilon$ die Akzeptierungswelle $q_0, Z_0, a_1, a_2, \dots, a_n$. Da $A$ nur einen Zustand hat, folgt aus $q_0 = q_1 = \dots = q_n$ und $Z_i = X$ für alle $i \in \{1, 2, \dots, n\}$ die Akzeptierungswelle $X, a_1, a_2, \dots, a_n$. Somit ist $w$ präfixfrei.

c) Die Sprache $L = \{a^n b^n | n \in \\mathbb{N}\}$ kann von einem $1$-Zustands-DPDA mit leerem Stack erkannt werden. Der $1$-Zustands-DPDA $A$ kann wie folgt definiert werden: $Q = \{q_0, q_1\}$, $\Sigma = \{a, b\}$, $\delta(q_0, a, X) = (q_0, aX)$, $\delta(q_0, b, X) = (q_1, \epsilon)$, $\delta(q_1, a, X) = (q_1, aX)$, $\delta(q_1, b, X) = (q_0, \epsilon)$.

d) Die Sprache $L = \{a^n b^{n+1} | n \in \\mathbb{N}\}$ kann nicht von einem $1$-Zustands-DPDA mit leerem Stack erkannt werden. Denn wenn $A$ ein $1$-Zustands-DPDA mit leerem Stack ist, so kann es kein Wort $w \in L$ akzeptieren, da es kein $w$ gibt, das mit einem leeren Stack beginnen und ein $b$ lesen kann, ohne dass der Stack leer wird.

e) Sei $\\mathcal{A} = (Q, \\Sigma, \\delta, s, F)$. Dann kann ein $1$-Zustands-NPDA $A'$ mit $Q' = Q$ und $\\delta'(q, a, X) = \{q_i | (q, a, q_i) \\in \\delta\}$ für alle $q \in Q$ und $a \in \\Sigma$ definiert werden. D.h., $A'$ liest jedes Symbol $a$ auf und geht in jeden Zustand $q_i$, der von $\\delta$ erreicht werden kann. Da $\\mathcal{A}$ nichtdeterministisch ist, kann $A'$ auch nichtdeterministisch sein.





****************************************************************************************
****************************************************************************************




Answer to Question 3


Antwort:

a) Zur Beweisung, dass $L$ nicht regulär ist, nehmen wir an, dass es eine reguläre Ausdruckung $R$ gibt, die $L$ beschreibt. Dann müsste $R$ mindestens zwei Terme enthalten, da $L$ nicht leer ist. Wir betrachten die Möglichkeit, dass $R$ zwei Terme $A$ und $B$ hat, die mit $\epsilon$ verbunden sind: $R = A\epsilon B$. Wir zeigen, dass $R$ nicht $L$ beschreibt.

Sei $w = \ta\tb\in L$. Dann haben wir $\abs{w}_{\ta} = \abs{w}_{\tb}$, also $c(w) = 0$. Da $w\in L(R)$, müsste $w$ auch in $L(A)$ oder $L(B)$ liegen. Wir betrachten beide Fälle.

Falls $w\in L(A)$, dann muss $w$ aus einem Wort $v$ und einem $\epsilon$ bestehen, das heißt $w = v\epsilon$. Da $w\in L$, muss $\abs{v}_{\ta} = \abs{v}_{\tb}$ gelten. Wir erhalten $\abs{w}_{\ta} = \abs{v}_{\ta} = \abs{v}_{\tb} = \abs{w}_{\tb}$, also $c(w) = 0$. Damit ist $w\in L(A)$ und $w\in L$ zugleich, also $w\in L(R)$.

Falls $w\in L(B)$, dann muss $w$ aus einem Wort $u$ und einem $\epsilon$ bestehen, also $w = u\epsilon$. Wieder muss $\abs{u}_{\ta} = \abs{u}_{\tb}$ gelten, also $\abs{w}_{\ta} = \abs{w}_{\tb}$ und $c(w) = 0$. Damit ist $w\in L(B)$ und $w\in L$ zugleich, also $w\in L(R)$.

Somit ist $L\subseteq L(R)$. Um die Umkehrung zu zeigen, nehmen wir an, dass $w\in L(R)$. Dann muss $w$ aus einem Wort $v$ und einem $\epsilon$ bestehen, also $w = v\epsilon$. Wir unterscheiden zwei Fälle.

Falls $v\in L$, dann ist $v\in L$ und $c(v) = 0$. Da $\abs{w}_{\ta} = \abs{v}_{\ta}$ und $\abs{w}_{\tb} = \abs{v}_{\tb}$, folgt $\abs{w}_{\ta} = \abs{w}_{\tb}$ und $c(w) = 0$. Damit ist $w\in L$.

Falls $v\notin L$, dann ist $c(v)\neq 0$. Wir unterscheiden zwei Fälle.

Falls $c(v) > 0$, dann ist $\abs{w}_{\ta} > \abs{w}_{\tb}$. Da $w\in L(R)$, muss $w\in L(B)$ sein, also $\abs{w}_{\tb} > 0$. Damit ist $\abs{w}_{\ta} > \abs{w}_{\tb}$, also $c(w) > 0$. Dies ist ein Widerspruch.

Falls $c(v) < 0$, dann ist $\abs{w}_{\ta} < \abs{w}_{\tb}$. Da $w\in L(R)$, muss $w\in L(A)$ sein, also $\abs{w}_{\ta} < 0$. Damit ist $\abs{w}_{\ta} < \abs{w}_{\tb}$, also $c(w) < 0$. Dies ist ebenfalls ein Widerspruch.

Somit ist $L(R)\subseteq L$. Da $L\subseteq L(R)$ und $L(R)\subseteq L$ gelten, folgt $L = L(R)$. Da $L$ nicht leer





****************************************************************************************
****************************************************************************************




Answer to Question 4


Antwort:

Die Instanz bzw. Lösung für das Green-Washing-Problem besteht aus einer Menge U von Elementen, einer Familie G von grünen Teilmengen G1, …, Gℓ ⊆ U und einer Familie R von Regenbogen-Teilmengen R1, …, Rm ⊆ U. Die Anzahl der Elemente in U muss größer als die Anzahl der Farben k sein, um mindestens eine grüne Menge ohne zwei grüne Elemente und mindestens eine Regenbogen-Menge ohne zwei Elemente der gleichen Farbe zu haben.

Beispiel:

Instanz: U = {a, b, c, d, e, f, g, h}, G = {{a, b}, {c, d}, {e, f}}, R = {{a, c, e}, {b, d, g}, {f, g, h}}

Lösung:

Instanz: U = {1, 2, 3, 4, 5, 6, 7, 8}, G = {{1, 2}, {3, 4}, {5, 6}}, R = {{1, 3, 5}, {2, 4, 7}, {6, 7, 8}}

Für das 3SAT-Problem besteht die Instanz aus einer Menge U an Aussagenlogischen Variablen und einer Menge C an Klauseln mit je maximal drei Literalen. Die Lösung ist eine Belegung der Variablen in U, sodass in jeder Klausel mindestens ein Literal wahr ist.

Beispiel:

Instanz: U = {x1, x2, x3}, C = {{x1, ¬x2, x3}, {x1, x2, ¬x3}, {¬x1, x2, x3}}

Lösung:

Instanz: U = {p, q, r}, C = {{p, ¬q, r}, {p, q, ¬r}, {¬p, q, r}}

Green-Washing ist NP-vollständig, da es sich um eine Verallgemeinerung des berühmten NP-schweren 3SAT-Problems handelt. Man kann Green-Washing in eine Instanz von 3SAT überführen, indem man für jedes Element x in U eine Variable xi einfügt und für jede grüne Menge Gi eine Klausel {xi, ¬xj, xk} für jedes grüne Element j in Gi und jedes anderes grünes Element k in U setzt. Somit kann man jedes Green-Washing-Problem in ein 3SAT-Problem überführen, und es ist bekannt, dass 3SAT NP-schwer ist. Daher ist Green-Washing auch NP-vollständig.

Hinweis:

Man kann Regenbogen-Mengen der Größe 2 verwenden, um zu erzwingen, dass ein Element grün und das andere nicht grün ist.





****************************************************************************************
****************************************************************************************




Answer to Question 5


Antwort:

Die Frage handelt von dem Problem der Quadrateinteilung eines Quadrats Q durch eine Menge M von Quadrate mit unterschiedlichen Seitenlängen. Das Ziel ist, so viele Flächen von Q wie möglich durch Quadrate aus M zu überdecken. Die Quadrate in M dürfen sich überschneiden und aus Q herausragen.

a) Algorithmus A platziert die Quadrate in M zeilenweise in aufsteigender Größe. Die erste Zeile beginnt direkt oberhalb der vorherigen Zeile und alle Quadrate einer Zeile werden auf der gleichen Höhe platziert. Eine neue Zeile wird begonnen, wenn die vorherige Zeile mindestens bis zur Hälfte von Q reicht. In der Instanz I mit M = {Q1, Q2, Q3, Q4}, wobei ℓ1 = 1, ℓ2 = 3, ℓ3 = 3, ℓ4 = 4 und ℓ = 7, platziert Algorithmus A die Quadrate wie folgt und überdeckt dabei eine Fläche von 23 in Q:

![Square Covering Example](figures/Square_Filling_Algo_Example.pdf)

Ergebnis: 23
Optimale Lösung: 25

b) In einer von Algorithmus A berechneten Lösung jeder Punkt in Q wird von höchstens zwei Quadraten überdeckt. Dies ist so, weil die Quadrate in jeder Zeile auf der gleichen Höhe platziert werden und die erste Zeile beginnt direkt oberhalb der vorherigen Zeile.

c) Algorithmus A ist ein polynomeller Approximationsalgorithmus mit relativer Gütegarantie 4 für das Quadrateinteilungsproblem. Dies ist so, weil die Anzahl der Quadrate in M, die auf einer Höhe platziert werden, linear ist und die Höhe der letzten Zeile, auf der Quadrate platziert werden, ist maximal 2 * ℓ. Somit hat Algorithmus A eine Laufzeit von O(n^2), wobei n die Anzahl der Quadrate in M ist. Die relative Gütegarantie von 4 folgt daraus, dass die Anzahl der Quadrate, die in Q überdeckt werden, maximal 4 mal so groß sein kann wie die Anzahl der Quadrate in der optimalen Lösung.

![Square Covering Example](figures/Square_Filling_blank.pdf)

In der oben gegebenen Instanz I mit M = {Q1, Q2, Q3, Q4}, wobei ℓ1 = 1, ℓ2 = 3, ℓ3 = 3, ℓ4 = 4 und ℓ = 7, platziert Algorithmus A die Quadrate wie folgt und überdeckt dabei eine Fläche von 23 in Q:

![Square Covering Example](figures/Square_Covering_Example_Solution.pdf)

In der optimalen Lösung können 25 Flächen von Q überdeckt werden:

![Square Covering Example](figures/Square_Covering_Optimal_Solution.pdf)

Die relative Gütegarantie von 4 folgt daraus, dass die Anzahl der Quadrate, die in Q überdeckt werden, maximal 4 mal so groß sein kann wie die Anzahl der Quadrate in der optimalen Lösung.

![Square Covering Example](figures/Square_Covering_Example_Approximation_Ratio.pdf)





****************************************************************************************
****************************************************************************************




Answer to Question 6


Antwort:

a) Eine Sprache $L'$ mit der Eigenschaft, dass sie $0$-präfixfrei ist, kann man z.B. durch die reguläre Ausdrucksdarstellung $$(0+1)^*$$ beschreiben.

b) Um zu zeigen, dass $\tmcode{M_\emptyset}\#w \in S$ für alle $w \in \Sigma^*$, müssen wir zeigen, dass $\tmcode{M_\emptyset}\#w$ kein Präfix von einem Wort aus $L(\tmcode{M_\emptyset})$ ist. Da $\tmcode{M_\emptyset}$ jedes Wort ablehnt, folgt daraus, dass $\tmcode{M_\emptyset}\#w$ kein Präfix von einem Wort aus $L(\tmcode{M_\emptyset})$ ist.

c) Um eine deterministische Turingmaschine $T_{M,w}$ zu konstruieren, die die obige Eigenschaft hat, kann man folgendermaßen vorgehen:

1. Lesen Sie das Wort $w$ ein.
2. Simulieren Sie die Turingmaschine $M$ auf dem leeren Band.
3. Wenn $M$ auf einem Endzustand landet, leiten Sie die Ausgabe $1$ ab und akzeptieren.
4. Wenn $M$ auf einem Zustand $q$ mit einem $0$-Symbol auf dem Band landet, führen Sie folgende Schritte aus:
   a. Schreiben Sie ein $1$ rechts neben dem $0$-Symbol.
   b. Setzen Sie den Zustand auf einen neuen Zustand $q'$.
   c. Wechseln Sie auf den nächsten Zustand $q'$ und lesen Sie das nächste Symbol.

Diese Konstruktion ist berechenbar, da sie von den beiden Eingaben $w$ und $\tmcode{M}$ abhängt.

d) Um zu zeigen, dass $S$ unentscheidbar ist, reduzieren wir auf die universelle Sprache $\tL_u$:

Sei $\tmcode{M}$ eine Turingmaschine. Wir wollen zeigen, dass es kein Algorithmus gibt, der für alle $w \in \Sigma^*$ entscheiden kann, ob $\tmcode{M}\#w \in S$ ist.

Falls $\tmcode{M}$ eine Turingmaschine ist, die $w$-präfixfrei ist, dann gilt $\tmcode{M}\#w \in S$. Wir wollen zeigen, dass es Turingmaschinen gibt, die für ein bestimmtes $w$ in $\Sigma^*$ kein Präfix von $\tmcode{M}\#w$ haben, aber selbst nicht $w$-präfixfrei sind.

Sei $w = 0^n1^n$ für ein $n \in \mathbb{N}$. Konstruieren Sie eine Turingmaschine $M_w$ wie folgt:

1. Lesen Sie das erste Symbol ein.
2. Wenn das erste Symbol ein $0$ ist, schreiben Sie ein $0$ rechts neben dem aktuellen Symbol und wechseln Sie auf den nächsten Zustand.
3. Wenn das erste Symbol ein $1$ ist, schreiben Sie ein $1$ rechts neben dem aktuellen Symbol und wechseln Sie auf den nächsten Zustand.
4. Wenn Sie das Wort $w$ gelesen haben, akzeptieren Sie.
5. In allen anderen Fällen lehnen Sie ab.

Diese Turingmaschine akzeptiert genau die Wörter, die ein Präfix von $\tmcode{M}\#w$ sind, aber selbst nicht $w$-präfixfrei sind. Da die universelle Sprache unentscheidbar ist, folgt daraus, dass $S$ unentscheidbar ist.





****************************************************************************************
****************************************************************************************




