Answer to Question 1
a) Um einen DEA anzugeben, der für das Wort $01$ die Menge der gültigen Suffixe $S_{01}(L_3)$ erkennt, müssen wir den Automatenkonstruktionsprozess durchgehen.

Zunächst definieren wir den Automaten $M = (Q, \Sigma, \delta, q_0, F)$:
- $Q = \{q_0, q_1, q_2, q_3\}$ (Zustände)
- $\Sigma = \{0, 1\}$ (Eingabealphabet)
- $q_0$ ist der Startzustand
- $F = \{q_3\}$ (Endzustand)
- Die transitierte Funktion $\delta$ ist gegeben durch:
  - $\delta(q_0, 0) = q_0$
  - $\delta(q_0, 1) = q_1$
  - $\delta(q_1, 0) = q_2$
  - $\delta(q_1, 1) = q_3$
  - $\delta(q_2, 0) = q_0$
  - $\delta(q_2, 1) = q_1$
  - $\delta(q_3, 0) = q_2$
  - $\delta(q_3, 1) = q_3$

Der DEA $M$ erkennt somit die Menge der gültigen Suffixe $S_{01}(L_3)$.

b) Die Menge der Wörter, die $S_{\varepsilon}(L)$ für eine beliebige Sprache $L$ enthält, ist die Menge der gültigen Suffixe, die durch das leere Wort gebildet werden. Diese Menge enthält nur das leere Wort $\varepsilon$ selbst.

c) Eine Sprache $L$ ist genau dann regulär, wenn $S_w(L)$ für alle $w \in \Sigma^*$ regulär ist. 

d) Um zu beweisen, dass es eine nichtreguläre Sprache $L$ gibt, bei der $S_w(L)$ für unendlich viele $w \in \Sigma^*$ regulär ist, können wir als Beispiel die Sprache $L = \{0^n 1^n \mid n \geq 0\}$ wählen. Diese Sprache $L$ ist bekanntermaßen nicht regulär.

Für diese Sprache $L$ ist $S_w(L)$ für unendlich viele $w \in \Sigma^*$ regulär, da für $w = 0^k$ mit $k \geq 0$ die Menge der gültigen Suffixe die reguläre Sprache $\{1^k\}$ ergibt.





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




Answer to Question 2
a) Um den DEA $A'$ mit der Zustandsmenge $Q = \{Z_0, Z_1, Z_2, X\}$ anzugeben, der die gleiche Sprache wie $A$ erkennt, können wir die Übergangsfunktionen von $A$ in die Zustandsübergänge von $A'$ übersetzen. Das bedeutet, dass die Zustände von $A'$ die Stacksymbole von $A$ repräsentieren. Hier ist der DEA $A'$:

- Zustandsmenge: $Q = \{Z_0, Z_1, Z_2, X\}$
- Anfangszustand: $Z_0$
- Zustandsübergänge:
    - $\delta'(Z_0, \sigma) = Z_1$ für $\sigma \in \{\sfA\}$
    - $\delta'(Z_1, \sigma) = Z_0$ für $\sigma \in \{\sfB\}$
    - $\delta'(Z_0, \sigma) = \epsilon$ für $\sigma \in \{\sfC\}$
    - In allen anderen Fällen: $\delta'(q, \sigma) = X$  
    Hierbei wird $\epsilon$ verwendet, um das oberste Symbol vom Stack zu entfernen.

b) Eine Sprache, die von einem 1-Zustands-DPDA mit leerem Stack erkannt wird, ist präfixfrei. Dies liegt daran, dass der DPDA bei Lesen eines Wortes $w$ nur einen eindeutigen Pfad durch den Automaten verfolgen kann, da er nur einen Zustand hat. Somit kann kein Präfix des Wortes $w$ zu einem akzeptierenden Zustand führen, da sonst das Wort selbst bereits akzeptiert worden wäre.

c) Ein Beispiel für eine nichtreguläre Sprache $L$, die von einem 1-Zustands-DPDA mit leerem Stack erkannt werden kann, ist die Sprache $L = \{a^n b^n \mid n \geq 0\}$. Ein entsprechender 1-Zustands-DPDA würde alle $a$'s auf den Stack pushen und dann beim Lesen der $b$'s die $a$'s wieder poppen, um die Übereinstimmung zu überprüfen.

d) Reguläre Sprachen, die nicht von einem 1-Zustands-DPDA mit leerem Stack erkannt werden können, sind z.B. Palindrome über dem Alphabet $\{0,1\}$. Da ein DPDA mit nur einem Zustand kein Gedächtnis hat, kann er nicht feststellen, ob ein Wort ein Palindrom ist.

e) Um zu zeigen, dass es für jeden gegebenen NEA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$ einen 1-Zustands-NPDA geben muss, der die gleiche Sprache erkennt, könnte man einen NPDA konstruieren, der in jedem Schritt alle möglichen Zustandsübergänge des NEA $\mathcal{A}$ nondeterministisch ausprobiert. Dabei wird der Stack nicht verändert, da nur ein Zustand betrachtet wird.





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




Answer to Question 3
**Antwort:**

a) Um zu zeigen, dass $L$ nicht regulär ist, können wir das Pumping-Lemma für reguläre Sprachen anwenden. Angenommen, $L$ wäre regulär. Dann müsste es eine Pumping-Zahl $p$ geben, sodass jedes Wort $z \in L$ mit $|z| \geq p$ aufgeteilt werden kann in $z = uvw$ mit den Eigenschaften: 

1. $|uv| \leq p$,
2. $|v| \geq 1$,
3. Für alle $i \geq 0$ ist $uv^iw \in L$.

Wir wählen das Wort $w = \ta^p \tb^p \in L$. Nach 1. und 2. bleibt $v$ innerhalb der ersten $p$ Zeichen, also besteht $uv$ nur aus $\ta$'s. Wenn wir $v$ mindestens einmal pumpen (d.h. $i>1$), würde das Verhältnis der Anzahl an $\ta$'s zur Anzahl an $\tb$'s nicht mehr übereinstimmen, also $uv^2w \notin L$. Daher kann $L$ nicht regulär sein.

b) Um $L(G_S) = \{w \in \Sigma^* \mid c(w) = 0\}$ zu zeigen, müssen wir zeigen, dass jedes Wort $w$ mit $c(w) = 0$ von $G_S$ erzeugt werden kann und dass jedes von $G_S$ erzeugte Wort $w$ auch $c(w) = 0$ erfüllt. 

Die eine Richtung: Jedes Wort $w$ in $L(G_S)$ wird von $G_A$ oder $G_B$ erzeugt. Wenn $w \in L(G_A)$, dann ist $c(w) = 1$. Wenn $w \in L(G_B)$, dann ist $c(w) = -1$. Da aber $c(w) = 0$, kann $w$ weder von $G_A$ noch von $G_B$ erzeugt werden, also muss $w$ direkt von $G_S$ erzeugt werden.

Die andere Richtung: Wir nehmen an, $w$ wird von $G_S$ erzeugt. Das heißt, es gibt eine Ableitungsfolge mit $S \Rightarrow^* w$. Aufgrund der Produktionsregeln von $G_S$ können jedoch nur Wörter erzeugt werden, für die $c(w) = 0$ gilt. Daher bedeutet die Ableitung $S \Rightarrow^* w$ auch $c(w) = 0$.

c) Die Sprache $L$ ist nicht kontextfrei. Dies kann z.B. durch Anwendung des Pumping-Lemmas für kontextfreie Sprachen gezeigt werden.

d) Um eine nicht-deterministische in-place Turingmaschine zu entwerfen, die die Sprache $L$ entscheidet, würden wir einen nicht-deterministischen Algorithmus konstruieren, der darauf abzielt, die Anzahl der Symbole $\ta$ und $\tb$ zu vergleichen. Die Turingmaschine würde die Eingabe überprüfen, indem sie von links nach rechts läuft und für jedes gelesene $\ta$ oder $\tb$ das entsprechende Zähler-Register erhöht. Wenn die Zähler am Ende übereinstimmen, akzeptiert die Maschine die Eingabe, andernfalls wird sie ablehnen.





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




Answer to Question 4
a) 
Für das Problem Green-Washing besteht eine Instanz im Allgemeinen aus:
- einer Menge $U$ von Elementen,
- einer Familie $G$ von Teilmengen $G_1, \dots, G_{\ell} \subseteq U$ (grüne Mengen),
- einer Familie $R$ von Teilmengen $R_1, \dots, R_m \subseteq U$ (Regenbogen-Mengen),
- und einem Parameter $k \in \mathbb{N}^+$.

Ein Beispiel ohne leere Mengen wäre:
- $U = \{1, 2, 3, 4\}$,
- $G = \{\{1, 2\}, \{2, 3, 4\}\}$,
- $R = \{\{1, 3\}, \{2, 4\}\}$,
- $k = 2$.

Eine Lösung der Beispiel-Instanz könnte sein:
- Elemente von $U$ mit zwei Farben so färben, dass jede grüne Menge mindestens ein grünes Element enthält und jede Regenbogen-Menge keine zwei Elemente der gleichen Farbe enthält.

Für das Problem 3SAT besteht eine Instanz im Allgemeinen aus:
- einer Menge $U$ an aussagenlogischen Variablen und
- einer Menge $C$ an Klauseln mit je maximal drei Literalen.

Ein Beispiel ohne leere Mengen wäre:
- $U = \{x, y, z\}$,
- $C = \{\{x, y, \neg z\}, \{\neg x, y, z\}\}$.

Eine Lösung der Beispiel-Instanz könnte sein:
- Belegung der Variablen $x=true$, $y=true$, $z=false$, so dass jede Klausel mindestens ein wahres Literal hat.

b) 
Um zu zeigen, dass Green-Washing NP-vollständig ist, nutzen wir die Reduktion von 3SAT auf Green-Washing.
Wir verwenden Regenbogen-Mengen der Größe 2, um sicherzustellen, dass ein Element grün ist und das andere nicht.

*Hinweis:* Wir können die Regenbogen-Mengen der Größe 2 nutzen, um zu erzwingen, dass ein Element grün und das andere nicht grün ist.





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




Answer to Question 5
a) 
Um den Algorithmus $\mathcal{A}$ auf der Instanz $I$ mit $M = \{Q_1, Q_2, Q_3, Q_4\}$ auszuführen, gehe wie folgt vor:
1. Sortiere die Quadrate aufsteigend nach ihrer Seitenlänge: $M = \{Q_1, Q_4, Q_2, Q_3\}$.
2. Initialisiere $x$ als unendlich, $y$ als 0 und $h$ als 0.
3. Beginne mit dem ersten Quadrat $Q_1$ mit Seitenlänge $\ell_1 = 1$:
    - $x \geq \left\lceil\frac{\ell}{2}\right\rceil$ ist falsch, also platziere $Q_1$ bei $(0,0)$.
    - Setze $x = x + \ell_1 = 1$.
4. Fahre mit $Q_4$ fort:
    - $x \geq \left\lceil\frac{7}{2}\right\rceil$ ist falsch, also platziere $Q_4$ bei $(1,0)$.
    - Setze $x = x + \ell_4 = 5$.
5. Gehe zu $Q_2$:
    - $x \geq \left\lceil\frac{7}{2}\right\rceil$ ist wahr, also setze $x = 0$, $y = y + h = 0$ und $h = \ell_2 = 3$.
    - Platziere $Q_2$ bei $(0,0)$.
    - Setze $x = x + \ell_2 = 3$.
6. Zuletzt $Q_3$:
    - $x \geq \left\lceil\frac{7}{2}\right\rceil$ ist wahr, also setze $x = 0$, $y = y + h = 3$ und $h = \ell_3 = 3$.
    - Platziere $Q_3$ bei $(0,3)$.

Das Ergebnis von $\mathcal{A}$ auf der Instanz $I$ ist eine Fläche von 7, die von $Q$ überdeckt wird.

Um eine optimale Überdeckung von $Q$ zu erstellen, müssen die Quadrate so platziert werden, dass sie die maximale Fläche von $Q$ abdecken. Diese optimale Überdeckung hängt von den genauen Maßen der Quadrate ab.

b) 
Um zu zeigen, dass in einer von $\mathcal{A}$ berechneten Lösung jeder Punkt in $Q$ von höchstens zwei Quadraten überdeckt wird, betrachten wir die Platzierung der Quadrate durch den Algorithmus. Da die Quadrate entlang der Höhe des Quadrats $Q$ platziert werden und sich überlappen dürfen, wird ein Punkt in $Q$ höchstens von zwei Quadrate überdeckt: dem Quadrat, das in derselben Zeile oder in der Zeile darüber liegt, und dem Quadrat, das sich direkt rechts davon befindet.

c)
Um zu zeigen, dass $\mathcal{A}$ ein polynomieller Approximationsalgorithmus mit relativer Gütegarantie 4 für \textsc{Square-Covering} ist, müssen wir zwei Fälle betrachten:

1. Fall: Quadraten ragen aus $Q$ heraus
In diesem Fall kann der Approximationsfaktor von $\mathcal{A}$ größer als 4 sein, da die Quadrate nicht vollständig in $Q$ liegen. Ein genauerer Beweis ist erforderlich.

2. Fall: Quadraten liegen komplett innerhalb von $Q$
Da in diesem Fall die Quadrate vollständig in $Q$ platziert werden, ist der Approximationsfaktor genau 4. Dies liegt daran, dass $\mathcal{A}$ für jedes Quadrat die linke untere Ecke als Platzierungsreferenz verwendet und von links nach rechts geht, sodass bei der maximalen Ausnutzung der Breite von $Q$ die optimale Lösung höchstens das Vierfache der Fläche abdecken kann, die $\mathcal{A}$ abdeckt.





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




Answer to Question 6
a) Eine Sprache $L' = \{1\}^*$ ist $0$-präfixfrei, da kein Wort aus $L'$ mit der Ziffer $0$ beginnt.

b) Die Turingmaschine $M_\emptyset$ akzeptiert kein Wort, das heißt $L(M_\emptyset) = \emptyset$. Da $\emptyset$ keine Wörter enthält und somit für alle $w \in \Sigma^*$ $w$ kein Präfix eines Wortes aus $\emptyset$ ist, ist $L(M_\emptyset)$ für alle $w$ $w$-präfixfrei. Somit ist $\text{M}_\emptyset\#w \in S$ für alle $w \in \Sigma^*$.

c) Um die Turingmaschine $T_{M,w}$ zu konstruieren, können wir wie folgt vorgehen:
   - $T_{M,w}$ simuliert die Turingmaschine $M$ auf dem Eingabewort $w$.
   - Falls $M$ das Wort $w$ akzeptiert, akzeptiert $T_{M,w}$ alle Eingabewörter, die nicht mit $w$ beginnen.
   - Falls $M$ das Wort $w$ nicht akzeptiert, akzeptiert $T_{M,w}$ alle Eingabewörter.

   Somit gilt $w \in L(M) \iff L(T_{M,w})$ ist nicht $w$-präfixfrei. Diese Konstruktion ist berechenbar, da wir $M$ und $w$ als Eingabe erhalten und dann die Schritte entsprechend ausführen.

d) Um zu zeigen, dass $S$ unentscheidbar ist, reduzieren wir auf die universelle Sprache $L_u$, die unentscheidbar ist. 
   Wir können die Reduktion durchführen, indem wir für ein Tupel $\text{M}\#w$ die Turingmaschine $T_{M,w}$ aus Teil (c) konstruieren und prüfen, ob $\text{M}\#w \in L_u$ gilt. Da $L_u$ unentscheidbar ist, folgt daraus, dass $S$ ebenfalls unentscheidbar ist.





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




