Answer to Question 1
a) Der DEA, der für das Wort 01 die Menge der gültigen Suffixe S_01(L_3) erkennt, sieht wie folgt aus:

- Startzustand q0
- Zustand q1 mit Übergang von q0 mit 1
- Zustand q2 mit Übergang von q1 mit 0 oder 1
- Zustand q0 mit Übergang von q2 mit 0 oder 1
- q1 ist der einzige Endzustand

Der Automat akzeptiert alle Wörter, bei denen nach dem Präfix 01 jedes dritte Zeichen eine 1 ist.

b) Für eine beliebige Sprache L enthält S_ε(L) genau die Wörter aus L selbst. Denn für das leere Wort ε gilt: wx ∈ L genau dann wenn x ∈ L.

c) Beweis:
"=>": Sei L regulär. Dann existiert ein DEA A mit L(A) = L. Für ein beliebiges w ∈ Σ* konstruieren wir einen DEA A_w für S_w(L) wie folgt: 
- Simuliere A auf Eingabe w bis zu einem Zustand q_w. 
- Mache q_w zum Startzustand von A_w.
- Die Zustände und Übergänge von A_w sind identisch zu A.
Dann gilt: x ∈ L(A_w) <=> wx ∈ L(A) <=> x ∈ S_w(L). Also ist S_w(L) regulär.

"<=": Sei S_w(L) für alle w ∈ Σ* regulär. Insbesondere ist dann S_ε(L) = L regulär.

d) Betrachte die Sprache L = {0^n1^n | n ≥ 0}. Diese ist nicht regulär. 
Für w = 0^k mit k ≥ 0 gilt aber: S_w(L) = {1^k} ist endlich und damit regulär.
Da es unendlich viele Wörter der Form 0^k gibt, ist S_w(L) für unendlich viele w regulär.





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




Answer to Question 2
a) Der DEA A' mit Zustandsmenge Q = {Z0, Z1, Z2, X}, der die gleiche Sprache wie der 1-Zustands-DPDA A erkennt, sieht wie folgt aus:

Übergangsfunktion:
- δ(Z0, A) = Z1
- δ(Z1, B) = Z0
- δ(Z0, C) = Z2
- In allen anderen Fällen geht der Automat in den Müllzustand X über.

Startzustand: Z0
Endzustand: Z2

b) Beweis, dass jede von einem 1-Zustands-DPDA mit leerem Stack erkannte Sprache präfixfrei ist:

Angenommen, die Sprache L wäre nicht präfixfrei. Dann gäbe es ein Wort w ∈ L und ein z ∈ Σ⁺, sodass wz ∈ L. Da der DPDA w akzeptiert, muss nach Lesen von w der Stack leer sein. Wenn der DPDA nun noch z liest, kann er nicht mehr akzeptieren, da der Stack bereits leer ist und keine Übergänge mehr möglich sind. Somit kann wz nicht in L sein. Widerspruch! Also muss L präfixfrei sein.

c) Eine nichtregulare Sprache, die von einem 1-Zustands-DPDA mit leerem Stack erkannt werden kann, ist L = {a^n b^n | n ≥ 0}.

Ein 1-Zustands-DPDA, der L erkennt:
- Alphabet Σ = {a, b}
- Stackalphabet Γ = {Z0, A}
- Übergangsfunktion:
  - δ(q, a, Z0) = (q, AZ0)
  - δ(q, a, A) = (q, AA)
  - δ(q, b, A) = (q, ε)
  - δ(q, ε, Z0) = (q, ε)

Der Automat legt für jedes gelesene a ein A auf den Stack. Für jedes b entfernt er ein A. Sind alle b's gelesen und der Stack ist leer, wird das Wort akzeptiert.

d) Beweis, dass es reguläre Sprachen gibt, die nicht von einem 1-Zustands-DPDA mit leerem Stack erkannt werden können:

Betrachte die reguläre Sprache L = {a, aa}. Angenommen, es gäbe einen 1-Zustands-DPDA, der L erkennt. Dann müsste er nach Lesen von a den Stack so verändern, dass er anschließend in der Lage ist, zu akzeptieren (leerer Stack) oder nach Lesen eines weiteren a zu akzeptieren. Das ist aber nicht möglich, da der Stack nach Lesen des ersten a entweder leer ist (und dann würde auch aa akzeptiert werden) oder nicht leer ist (dann würde a nicht akzeptiert werden). Also kann L nicht von einem 1-Zustands-DPDA mit leerem Stack erkannt werden.

e) Beweis, dass es zu jedem NEA einen äquivalenten 1-Zustands-NPDA gibt:

Sei A = (Q, Σ, δ, s, F) ein beliebiger NEA. Wir konstruieren einen 1-Zustands-NPDA A', der die gleiche Sprache erkennt:

- A' hat nur einen Zustand q
- Stackalphabet Γ = Q ∪ {Z0}
- Übergangsfunktion δ':
  - Für alle p ∈ Q, a ∈ Σ mit δ(p, a) = {q1, ..., qk}: δ'(q, a





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




Answer to Question 3
a) Um zu zeigen, dass L nicht regulär ist, können wir das Pumping-Lemma für reguläre Sprachen verwenden. Angenommen L wäre regulär, dann gäbe es eine Konstante n, so dass sich jedes Wort w ∈ L mit |w| ≥ n in xyz zerlegen lässt mit |xy| ≤ n, |y| ≥ 1 und xy^i z ∈ L für alle i ≥ 0.
Wählen wir nun w = a^n b^n. Dieses Wort liegt in L, da es gleich viele a's wie b's enthält. Egal wie wir w in xyz zerlegen, y wird nur a's oder nur b's enthalten. Pumpen wir y auf, erhalten wir ein Wort mit ungleich vielen a's und b's, das nicht mehr in L liegt. Damit ist L nicht regulär.

b) Um L(G_S) = {w ∈ Σ* | c(w) = 0} zu zeigen, müssen wir beide Inklusionen zeigen:

"⊆": Sei w ∈ L(G_S). Dann gibt es eine Ableitung S =>* w. Wir zeigen per Induktion über die Ableitungslänge, dass c(w) = 0 gilt. 
Induktionsanfang: Ist die Ableitung 1 Schritt lang, muss w = ε gelten. Dann ist c(w) = 0.
Induktionsschritt: Ist die Ableitung länger, muss der erste Schritt S -> aB oder S -> bA sein. Im ersten Fall ist w = aw' mit w' ∈ L(G_B). Nach Gleichung (2) gilt c(w') = -1, also c(w) = c(a) + c(w') = 1 - 1 = 0. Der zweite Fall ist analog.

"⊇": Sei w ∈ Σ* mit c(w) = 0. Wir zeigen per Induktion über |w|, dass w ∈ L(G_S).
Induktionsanfang: |w| = 0, also w = ε. Dann ist w ∈ L(G_S) wegen S -> ε.  
Induktionsschritt: Ist |w| > 0 und w beginnt mit a, muss w = aw' mit c(w') = c(w) - c(a) = -1 sein. Nach Gleichung (2) und Induktionsvoraussetzung ist w' ∈ L(G_B), also w ∈ L(G_S) wegen S -> aB. Beginnt w mit b, argumentiert man analog mit Gleichung (1).

c) Ja, L ist kontextfrei. Die Grammatik G aus Teilaufgabe b) erzeugt nach dem Ergebnis aus b) genau die Sprache L, also ist L kontextfrei.

d) Eine nicht-deterministische in-place Turingmaschine für L arbeitet wie folgt:
- Starte mit dem Kopf auf dem ersten Zeichen
- Solange das aktuelle Zeichen kein Blank ist:
  - Ist es ein a, dann ersetze es nicht-deterministisch durch X oder Y und gehe nach rechts 
  - Ist es ein b, dann ersetze es nicht-deterministisch durch X oder Y und gehe nach rechts
- Gehe zum Bandanfang zurück 
- Solange das aktuelle Zeichen kein Blank ist:
  - Ist es X, dann gehe nach rechts
  - Ist es Y, dann lehne ab
- Ist das Band leer (alle Zeichen durch X ersetzt), dann akzeptiere, sonst lehne ab

Die Maschine rät für jedes a und b, ob es durch X oder Y ersetzt wird. Nur wenn für





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




Answer to Question 4
a) Hier ist die ausgefüllte Tabelle für die Instanzen und Lösungen von 3SAT und Green-Washing:

|                    | 3SAT                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                





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




Answer to Question 5
a) Ich würde die Ausführung von Algorithmus $\mathcal{A}$ auf der gegebenen Instanz $I$ wie folgt in das Quadrat $Q$ einzeichnen:
- $Q_1$ mit Seitenlänge 1 in die linke untere Ecke von $Q$
- $Q_2$ und $Q_3$ mit Seitenlänge 3 direkt oberhalb von $Q_1$ nebeneinander
- $Q_4$ mit Seitenlänge 4 in einer neuen Zeile oberhalb von $Q_2$ und $Q_3$, da diese zusammen bereits die Hälfte der Breite von $Q$ überdecken

Eine optimale Überdeckung würde ich wie folgt einzeichnen:
- $Q_4$ mit Seitenlänge 4 in die linke untere Ecke von $Q$
- $Q_2$ und $Q_3$ mit Seitenlänge 3 direkt oberhalb von $Q_4$ nebeneinander
- $Q_1$ mit Seitenlänge 1 in die verbleibende Lücke rechts oben

Es gilt $\mathcal{A}(I) = 22$ (Fläche von $Q_1$, $Q_2$, $Q_3$ innerhalb $Q$ plus Fläche von $Q_4$ innerhalb $Q$) und $\mathrm{OPT}(I) = 7 \cdot 7 = 49$.

b) Angenommen es gäbe einen Punkt in $Q$, der von mindestens drei platzierten Quadraten überdeckt wird. Dann müssten sich mindestens drei Quadrate überlappen. Das ist aber nicht möglich, da:
1) Quadrate einer Zeile sich nie überlappen, da sie nebeneinander platziert werden. 
2) Das erste Quadrat einer neuen Zeile immer direkt oberhalb des ersten Quadrats der vorherigen Zeile platziert wird. Zusammen mit 1) überlappen sich also auch Quadrate verschiedener Zeilen höchstens paarweise.

c) Fall 1: $\mathcal{A}$ platziert alle Quadrate so, dass sie nicht aus $Q$ herausragen. Dann überdeckt $\mathcal{A}$ mindestens die Hälfte der Fläche von $Q$, denn:
- Jede Zeile außer der letzten überdeckt mindestens die Hälfte der Breite von $Q$ (Zeilenbedingung).
- Jeder Punkt wird höchstens doppelt überdeckt (b), also ist die überdeckte Fläche mindestens halb so groß wie die Summe der Flächen der platzierten Quadrate.
- Die Summe der Flächen aller Quadrate ist mindestens so groß wie die Fläche von $Q$, sonst wäre die Platzierung nicht vollständig innerhalb $Q$ möglich.
Insgesamt gilt also $\mathcal{A}(I) \geq \frac{1}{2} \mathrm{OPT}(I)$.

Fall 2: $\mathcal{A}$ platziert mindestens ein Quadrat so, dass es aus $Q$ herausragt. Sei $Q_i$ das erste solche Quadrat. Dann überdecken die Quadrate $Q_1, \ldots, Q_{i-1}$ mindestens die Hälfte der Fläche von $Q$ (wie in Fall 1). Außerdem überdeckt $Q_i$ mindestens ein Viertel der Fläche von $Q$, denn:
- $Q_i$ ragt aus $Q$ heraus $\Rightarrow \ell_i > \frac{\ell}{2}$ (sonst Widerspruch zu Zeilenbedingung)
- $





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




Answer to Question 6
a) Eine Sprache L', die 0-präfixfrei ist, wäre zum Beispiel:
L' = {1, 11, 111, 1111, ...} = {1^n | n ≥ 1}
Da kein Wort in L' mit 0 beginnt, kann 0 kein Präfix eines Wortes aus L' sein.

b) Die leere Sprache L(M_∅) = ∅ ist w-präfixfrei für jedes Wort w ∈ Σ*, da sie keine Wörter enthält. Egal welches w wir an ein Wort aus L(M_∅) anhängen, das resultierende Wort kann nicht in L(M_∅) sein, da L(M_∅) leer ist. Somit ist ⟨M_∅⟩#w ∈ S für alle w ∈ Σ*.

c) Die Turingmaschine T_{M,w} kann wie folgt konstruiert werden:
1. Simuliere M auf Eingabe w. 
2. Falls M die Eingabe w akzeptiert, akzeptiere w und lehne alle anderen Eingaben ab.
3. Falls M die Eingabe w ablehnt, lehne alle Eingaben ab.

Wenn w ∈ L(M), dann akzeptiert T_{M,w} nur das Wort w. Somit ist w ein Präfix jedes akzeptierten Wortes und L(T_{M,w}) ist nicht w-präfixfrei.  
Wenn w ∉ L(M), dann lehnt T_{M,w} alle Eingaben ab, also L(T_{M,w}) = ∅. Die leere Menge ist w-präfixfrei für jedes w.
Die Konstruktion ist berechenbar, da wir einfach M auf w simulieren und abhängig vom Ergebnis T_{M,w} konstruieren.

d) Wir zeigen S ≤_m ¬L_u, dann folgt die Unentscheidbarkeit von S. Sei ⟨M⟩#w ∈ Σ^*. Definiere die Funktion
f(⟨M⟩#w) = ⟨T_{M,w}⟩#w
wobei T_{M,w} die TM aus c) ist. Dann gilt:
⟨M⟩#w ∈ S 
⇔ L(M) ist w-präfixfrei
⇔ w ∉ L(M) (nach c)
⇔ ⟨M⟩#w ∉ L_u
⇔ f(⟨M⟩#w) ∉ L_u

Also ist f eine Reduktion von S auf ¬L_u. Da L_u unentscheidbar ist, muss auch S unentscheidbar sein.





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




