Exam 2024_retake.txt — openai/gpt-oss-120b

Exercise a b c d e f g Total
1: Quiz: Reguläre und kontextfreie Sprachen 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 2.0/3.0 0.0/3.0 12.0/16.0
2: DFA-Algorithmen 6.0/6.0 1.0/1.0 4.0/4.0 2.0/2.0 0.0/5.0 13.0/18.0
3: Rekursive Funktionen 1.0/1.0 5.0/6.0 6.0/6.0 12.0/13.0
4: CFG-Algorithmen 2.0/2.0 2.0/2.0 3.0/3.0 3.0/3.0 2.0/3.0 12.0/13.0
5: Verlorene Buchsten 1.0/1.0 2.0/2.0 5.0/7.0 1.0/2.0 9.0/12.0
6: Quiz: Berechenbarkeit und Komplexität 2.0/2.0 2.0/2.0 0.0/2.0 2.0/2.0 0.0/2.0 4.0/4.0 10.0/14.0
7: Reduktion 4.0/4.0 3.0/3.0 7.0/7.0 14.0/14.0
8: Bonus 0.0/2.0 1.0/1.0 0.0/2.0 1.0/5.0
Exam total 83.0/105.0

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma := \{a, b\}.

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (2.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(aba)abX=(a^*b^*a)^*ab  
Y=((ab)a    bb)Y=((a|b)a^* \;|\; bb)^*  
Z=Z=\emptyset
1: mismatch
1: could not parse value ((a|b)a^* \;|\; bb)^* for type re

Subproblem g (0.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
wrong answer for choice (0)
Reversibler NFA NN für L=(aa)(bb)L = (aa)^*(bb)^*  

- Zustandsmenge: Q={q0,q1,q2}Q = \{q_0, q_1, q_2\}  
- Startzustand: q0q_0  
- Endzustände: F={q0}F = \{q_0\}  

- Übergangsfunktion δ\delta:  

δ(q0,a)={q1},δ(q1,a)={q0},δ(q0,b)={q2},δ(q2,b)={q0},δ(q1,b)=,δ(q2,a)=.
\begin{aligned}
\delta(q_0, a) &= \{q_1\}, & \delta(q_1, a) &= \{q_0\}, \\
\delta(q_0, b) &= \{q_2\}, & \delta(q_2, b) &= \{q_0\}, \\
\delta(q_1, b) &= \emptyset, & \delta(q_2, a) &= \emptyset.
\end{aligned}


Alle übrigen Übergänge sind leer (\emptyset).  

Warum ist der NFA reversibel?  
Für jedes Symbol x{a,b}x \in \{a,b\} gilt:
- Wenn q2δ(q1,x)q_2 \in \delta(q_1,x) (z.B. q1aq0q_1 \xrightarrow{a} q_0), dann ist zugleich q1δ(q2,x)q_1 \in \delta(q_2,x) (z.B. q0aq1q_0 \xrightarrow{a} q_1).  
- Analog für die bb-Übergänge zwischen q0q_0 und q2q_2.  

Damit erfüllt NN die Definition eines reversiblen NFA.

Sprachakzeptanz:  
- Durch abwechselnde aa-Übergänge zwischen q0q_0 und q1q_1 wird nur eine gerade Anzahl von aa’s akzeptiert (Endzustand muss q0q_0 sein).  
- Nachdem ein bb gelesen wurde, wechselt man zu q2q_2; weitere bb’s pendeln zwischen q2q_2 und q0q_0, also ebenfalls nur gerade Anzahl von bb’s führen zum Endzustand q0q_0.  
- Sobald man sich in q2q_2 befindet, gibt es keinen aa-Übergang, sodass nach Beginn des bb-Blocks kein weiteres aa mehr gelesen werden kann.  

Somit akzeptiert NN exakt die Sprache (aa)(bb)(aa)^*(bb)^*.

Exercise 2: DFA-Algorithmen


Subproblem a (6.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, a -> q4
    q0, b -> q1
    q1, a -> q4
    q1, b -> q2
    q2, a -> q5
    q2, b -> q3
    q3, a -> q7
    q3, b -> q3
    q4, a -> q4
    q4, b -> q4
    q5, a -> q6
    q5, b -> q4
    q6, a -> q5
    q6, b -> q7
    q7, a -> q7
    q7, b -> q7
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 0, 1, 2, 3
    q4: \emptyset
    q5: 3
    q6: 1, 2
    q7: 1, 2, 3

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
The DFA is not minimal.  In the reachable part of M the following states are equivalent:
- q₂ and q₆ have identical future behaviour,
- q₃ and q₇ have identical future behaviour.

Merging each pair yields a smaller DFA, therefore the original DFA M is not minimal.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0,0), (1,2), (2,1), (2,2), (2,0)
Startzustand: (0,0)
Finalzustände: (1,2), (2,1), (2,2)
Transitionen:
(0,0), a -> (1,2)
(0,0), b -> (0,0)
(1,2), a -> (2,1)
(1,2), b -> (2,2)
(2,1), a -> (2,2)
(2,1), b -> (2,0)
(2,2), a -> (2,1)
(2,2), b -> (2,2)
(2,0), a -> (2,2)
(2,0), b -> (2,0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa  
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab  
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (0.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n)=n+1f(n)=n+1

Begründung:<br>
Gegeben ein DFA  
M=(Q,{a,b,c},δ,q0,F)M=(Q,\{a,b,c\},\delta,q_{0},F) mit Q=n|Q|=n.

1. c‑Closure berechnen  
   Für jeden Zustand qQq\in Q bestimmen wir die Menge  
   C(q)={pQqcp},
   C(q)=\{p\in Q \mid q \xrightarrow{c^{*}} p\},
   
   also alle Zustände, die von qq über beliebig viele c‑Übergänge (auch 0) erreichbar sind.  
   Da die c‑Übergänge allein einen gerichteten Graphen bilden, lässt sich C(q)C(q) für alle qq in Zeit O(n2)O(n^{2}) mittels einer Tiefensuche bzw. Floyd‑Warshall ermitteln.

2. DFA ohne c‑Eingaben konstruieren  
   Wir definieren einen neuen Automaten  
   M=(Q{qsink},{a,b},δ,q0,F)
   M'=(Q\cup\{q_{\text{sink}}\},\{a,b\},\delta',q_{0},F')
   
   mit den gleichen Zuständen wie MM (plus einem einzigen Fehlzustand qsinkq_{\text{sink}}, falls ein Übergang nicht definiert ist).

   * Übergangsfunktion  
     Für x{a,b}x\in\{a,b\} und qQq\in Q setzen wir
     δ(q,x)={ein beliebiger Zustand pC(δ(q,x))wenn δ(q,x) definiert ist,qsinksonst.
     \delta'(q,x)=
     \begin{cases}
        \text{ein beliebiger Zustand } p\in C(\delta(q,x)) & \text{wenn }\delta(q,x)\text{ definiert ist},\\[4pt]
        q_{\text{sink}} & \text{sonst}.
     \end{cases}
     
     Das bedeutet: wir führen zunächst den normalen xx-Übergang von MM aus und „überspringen“ danach beliebig viele c‑Übergänge, indem wir sofort in die entsprechende c‑Closure gehen.

   * Endzustände  
     Ein Zustand qq ist Endzustand von MM', genau dann wenn die c‑Closure von qq einen Endzustand von MM enthält:
     F={qQC(q)F}    {qsink  :  qsinkF}.
     F'=\{\,q\in Q \mid C(q)\cap F\neq\emptyset\,\}\;\cup\;\{q_{\text{sink}}\;:\;q_{\text{sink}}\in F\}.
     

3. Korrektheit  
   Für ein Wort w{a,b}w\in\{a,b\}^{*} lässt sich ein Wort w^{a,b,c}\hat w\in\{a,b,c\}^{*} mit Rc(w^)=wR_{c}(\hat w)=w exakt dann erzeugen, wenn man in MM von q0q_{0} aus die Buchstaben von ww liest und zwischendurch beliebig viele c‑Übergänge ausführt.  Durch die Definition von δ\delta' und FF' akzeptiert MM' genau die Wörter, für die ein solches w^\hat w existiert; also
   L(M)=Rc(L(M)).
   L(M') = R_{c}\bigl(L(M)\bigr).
   

4. Zustandsanzahl  
   Der konstruierte Automat verwendet höchstens die ursprünglichen nn Zustände von MM plus ggf. einen zusätzlichen Fehlzustand, also höchstens n+1n+1 Zustände.  Damit erfüllt er die geforderte Schranke f(n)=n+1f(n)=n+1.

Der beschriebene Algorithmus läuft in polynomialer Zeit (O(n²) für die Closure‑Berechnung und O(n) für das Anlegen der neuen Übergänge) und liefert einen DFA MM' mit f(n)=n+1\le f(n)=n+1 Zuständen, der exakt die Sprache Rc(L(M))R_{c}(L(M)) akzeptiert.

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache LΣL\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxwv,wΣx{0,ε}vwL}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,010,001}N(\{01, 0\})=\{0,00,01,010,001\}

Subproblem b (5.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und aΣa\in \Sigma.
Null():=\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a0aa0\Null(a) := a \mid 0a \mid a0
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r1Null(r2)\Null(r_1 r_2) := \Null(r_1)\, r_2 \mid r_1\, \Null(r_2)
Null(r):=(r)Null(r)(r)\Null(r^*) := (r^{*})\, \Null(r)\, (r^{*})

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut():=\Cut(\emptyset) := \emptyset
Cut(0):=\Cut(0) := \emptyset
Cut(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,vΣu,v\in\Sigma^* mit u1vL(r)u1v\in L(r) gilt, dass uL(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(Cut(r1r2))u\in L(\Cut(r_1r_2)).
**Induktionshypothese(n) für den Fall \(r = r_{1}r_{2}\):**  

1. *(IH 1)* Für alle \(u_{1}v\in L(r_{1})\) mit \(u_{1},v\in\Sigma^{*}\) gilt  
   \(\displaystyle u_{1}\in L(\Cut(r_{1})).\)

2. *(IH 2)* Für alle \(u_{2}v\in L(r_{2})\) mit \(u_{2},v\in\Sigma^{*}\) gilt  
   \(\displaystyle u_{2}\in L(\Cut(r_{2})).\)

---

**Beweis des Falls \(r = r_{1}r_{2}\):**  

Sei \(u1v\in L(r_{1}r_{2})\) mit \(u,v\in\Sigma^{*}\).  
Nach der Definition der Konkatenation gibt es Wörter \(x\in L(r_{1})\) und \(y\in L(r_{2})\) derart, dass  

\[
u1v = xy .
\]

Der einzelne Buchstabe \(1\) befindet sich entweder in \(x\) **oder** in \(y\). Wir behandeln beide Möglichkeiten getrennt.

---

**Fall 1 – die 1 liegt in \(x\).**  

Dann lässt sich \(x\) schreiben als \(x = u_{1}1v_{1}\) mit \(u_{1},v_{1}\in\Sigma^{*}\) und \(y\) beliebig.  
Da \(x\in L(r_{1})\) und \(u_{1}1v_{1}\in L(r_{1})\), dürfen wir die Induktionshypothese **(IH 1)** anwenden und erhalten  

\[
u_{1}\in L(\Cut(r_{1})).
\]

Weil nach Definition  

\[
\Cut(r_{1}r_{2}) = \Cut(r_{1}) \mid r_{1}\Cut(r_{2}),
\]

ist jedes Wort aus \(L(\Cut(r_{1}))\) zugleich ein Wort aus \(L(\Cut(r_{1}r_{2}))\). Also  

\[
u = u_{1}\in L(\Cut(r_{1}r_{2})).
\]

---

**Fall 2 – die 1 liegt in \(y\).**  

Dann hat \(y\) die Form \(y = u_{2}1v_{2}\) mit \(u_{2},v_{2}\in\Sigma^{*}\) und \(x\) enthält kein 1.  
Wir haben also  

\[
x\in L(r_{1}) \quad\text{und}\quad u_{2}1v_{2}\in L(r_{2}).
\]

Aus \(u_{2}1v_{2}\in L(r_{2})\) und **(IH 2)** folgt  

\[
u_{2}\in L(\Cut(r_{2})).
\]

Damit ist das Wort \(xu_{2}\) ein Element von  

\[
L(r_{1})\,L(\Cut(r_{2})) \subseteq L(\Cut(r_{1}) \mid r_{1}\Cut(r_{2}))
      = L(\Cut(r_{1}r_{2})).
\]

Da das ursprüngliche Präfix vor dem Symbol \(1\) genau \(u = xu_{2}\) ist, erhalten wir  

\[
u\in L(\Cut(r_{1}r_{2})).
\]

---

In beiden Fällen folgt aus der Annahme \(u1v\in L(r_{1}r_{2})\), dass \(u\in L(\Cut(r_{1}r_{2}))\). Damit ist die zu zeigende Aussage für den Fall \(r = r_{1}r_{2}\) bewiesen. ∎

Exercise 4: CFG-Algorithmen

In den Teilaufgaben (a)-(d) geht es darum, eine kontextfreie Grammatik (CFG) in Chomsky-Normalform (CNF) zu konvertieren. Wir führen jeden Schritt einzeln aus, und jeweils auf einer anderen Grammatik – Sie können also die Aufgabenteile unabhängig voneinander bearbeiten.

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (Xα)P(X\rightarrow\alpha)\in P, mit XVX\in V und α(ΣV)\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) αΣV\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) α2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) αε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) αV\alpha\notin V; es gibt keine Kettenproduktionen.

Achtung: Die Teilaufgaben fragen jeweils spezifisch nach dem Ergebnis, das sich durch die Ausführung des Algorithmus aus der Vorlesung ergibt, nicht nach einer beliebigen äquivalenten CFG, die den Bedingungen genügt. Details, wie etwa die Namen der Variablen oder die Reihenfolge, in der Produktionen betrachtet werden, können Sie frei wählen.
Wir nennen AϵA \rightarrow \epsilon eine ϵ\epsilon-Produktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG GG' konstruieren, die keine ϵ\epsilon-Produktionen enthält, so dass gilt
L(G)=L(G){ϵ}L(G') = L(G)\setminus\{\epsilon\}
\end{Lemma}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{BϵB \rightarrow \epsilon} und \alert{AαBβA \rightarrow \alpha B \beta} in P^\hat{P}, so füge auch \alert{AαβA \rightarrow \alpha\beta} hinzu.
\end{enumerate}
Offensichtlich gilt L(G^)=L(G)L(\hat{G}) = L(G): Jede neue Produktion kann von 2 alten Productionensimuliert werden.

Wir definieren GG' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen ABA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG GG' konstruieren, die keine Kettenproduktionen enthält, so dass gilt L(G)=L(G)L(G') = L(G).
\end{Lemma}
\begin{Beweis}
Wir erweitern PP induktiv zu eine Obermenge P^\hat{P}:
\begin{enumerate}
\item Jede Produktion aus PP ist in P^\hat{P}
\item Sind \alert{ABA \rightarrow B} und \alert{BαB \rightarrow \alpha} in P^\hat{P} mit αA\alpha \neq A, so füge auch \alert{AαA \rightarrow \alpha} hinzu.
\end{enumerate}
Das Ergebnis GG' ist G^\hat{G} ohne die (nun überflüssigen) Kettenproduktionen.

\paragraph{Konstruktion einer Chomsky-Normalform}

Eingabe: Eine kontextfreie Grammatik G=(V,Σ,P,S)G = (V,\Sigma,P,S)
\begin{enumerate}
\item Füge für jedes aΣa\in\Sigma, das in einer rechten Seite der Länge 2\geq2 vorkommt, ein neues Nichtterminal AaA_a zu VV hinzu, ersetze aa in allen rechten Seiten der Länge 2\geq 2 durch AaA_a, und füge AaaA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
AB1B2Bk(k3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
AB1C2, C2B2C3,...,Ck1Bk1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck1C_2, ..., C_{k-1} neue Nichtterminale sind.
\item Eliminiere alle ϵ\epsilon-Produktionen.
\item Eliminiere alle Kettenproduktionen.
\end{enumerate}

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
SaXXaabS \rightarrow aX \mid Xa \mid ab
XSSSεbXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG GaG'_a an, so dass L(Ga)=L(Ga)L(G_a) = L(G'_a) gilt und GaG'_a Bedingung (1) erfüllt.
SAaXXAaAaAbS \rightarrow A_aX \mid XA_a \mid A_aA_b
XSSSεAbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_bXX
AaaA_a \rightarrow a
AbbA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
SABAAεS \rightarrow A \mid BAA \mid \varepsilon
ASABBaA \rightarrow SABB \mid a
BASbB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG GbG'_b an, so dass L(Gb)=L(Gb)L(G_b) = L(G'_b) und GbG'_b Bedingungen (1) und (2) erfüllt.
S    A    BX1    εS \;\rightarrow\; A \;\mid\; B\,X_1 \;\mid\; \varepsilon
X1    AAX_1 \;\rightarrow\; A\,A
A    SC2    aA \;\rightarrow\; S\,C_2 \;\mid\; a
C2    AC3C_2 \;\rightarrow\; A\,C_3
C3    BBC_3 \;\rightarrow\; B\,B
B    AS    bB \;\rightarrow\; A\,S \;\mid\; b

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
SABDES \rightarrow AB \mid DE
AABaεA \rightarrow AB \mid a \mid \varepsilon
BbBBDB \rightarrow b \mid BB \mid D
CAcC \rightarrow A \mid c
DBCBSD \rightarrow BC \mid BS
ESSCAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG GcG'_c an, so dass L(Gc)=L(Gc)L(G_c) = L(G'_c) und GcG'_c Bedingungen (1), (2) und (3) erfüllt.
SABDEBDS \rightarrow AB \mid DE \mid B \mid D
AABaBA \rightarrow AB \mid a \mid B
BbBBDB \rightarrow b \mid BB \mid D
CAcC \rightarrow A \mid c 
DBCBSBD \rightarrow BC \mid BS \mid B 
ESSCAACE \rightarrow SS \mid CA \mid A \mid C

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
SaBABS \rightarrow a \mid BA \mid B
AaAAA \rightarrow a \mid AA
BbSCAB \rightarrow b \mid SC \mid A
CBSSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG GdG'_d in CNF an, so dass L(Gd)=L(Gd)L(G_d) = L(G'_d) gilt.
S    aBAbSCAAS \;\rightarrow\; a \mid BA \mid b \mid SC \mid AA 
A    aAAA \;\rightarrow\; a \mid AA 
B    bSCaAAB \;\rightarrow\; b \mid SC \mid a \mid AA 
C    SSbSCaAAC \;\rightarrow\; SS \mid b \mid SC \mid a \mid AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
SABCS \rightarrow AB\mid C
AaAASA \to aA \mid AS
BbSB \to bS
CaCbεC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.
Erzeugend: S,B,CS, B, C  
Erreichbar: S,A,B,CS, A, B, C  
Nützlich: S,B,CS, B, C
2: mismatch

Exercise 5: Verlorene Buchsten

Sei Σ:={a,b}\Sigma:=\{a,b\}. Für eine Sprache LΣL\subseteq\Sigma^* bezeichnet Del(L)\Del(L) die Sprache,
die man erhält, wenn man den Wörtern aus LL genau einmal das Wort abab an einer beliebigen Stelle entfernt. Formal definieren wir
Del(L):={vwv,wΣvabwL}\Del(L):= \{vw \mid v,w\in \Sigma^* \wedge vabw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache Del({abbaba,baa,ab,a,b})\Del(\{abbaba,baa,ab,a,b\}) explizit auf:
Del({abbaba,baa,ab,a,b})={ε,baba,abba}\Del(\{abbaba,baa,ab,a,b\}) = \{\varepsilon,baba,abba\}

Subproblem b (2.0/2.0P)

Wir definieren DelTwo(L):={uvwu,v,wΣuabvabwL}\DelTwo(L):=\{uvw \mid u,v,w\in \Sigma^* \wedge u ab v ab w\in L \}. Zeigen Sie oder widerlegen Sie mit einem Gegenbeispiel: Für jede endliche Sprache LΣL\subseteq\Sigma^* gilt
Del(Del(L))=DelTwo(L)\Del(\Del(L))=\DelTwo(L).
WahrFalsch
Die Beh ist falsch.  

Ein Gegenbeispiel ist die endliche Sprache  

L={aabb}.
L=\{\,aabb\,\}.


*   Berechnung von Del(Del(L))\Del(\Del(L)):  
    - Das Wort aabbaabb enthält das Teilwort abab (Position 2‑3).  
    - Entfernen wir dieses abab, erhalten wir das Wort abab.  
    - Das resultierende Wort abab enthält erneut das Teilwort abab; nach erneutem Entfernen erhalten wir ε\varepsilon.  

    Also εDel(Del(L))\varepsilon \in \Del(\Del(L)).

*   Berechnung von DelTwo(L)\DelTwo(L):  
    - Für DelTwo(L)\DelTwo(L) muss das Ausgangswort die Form uabvabwu\,ab\,v\,ab\,w haben, also mindestens zwei vorkommende Teilwörter abab.  
    - Das Wort aabbaabb enthält nur ein einziges abab und lässt sich nicht als uabvabwu\,ab\,v\,ab\,w schreiben.  

    Deshalb εDelTwo(L)\varepsilon \notin \DelTwo(L).

Da ε\varepsilon in Del(Del(L))\Del(\Del(L)) liegt, aber nicht in DelTwo(L)\DelTwo(L), gilt die Gleichheit nicht für alle endlichen Sprachen LL.

Del(Del(L))DelTwo(L) im Allgemeinen
\boxed{\Del(\Del(L))\neq\DelTwo(L)\text{ im Allgemeinen}}


Damit ist die Aussage falsch.

Subproblem c (5.0/7.0P)

Sei G=(V,Σ,P,S)G=(V,\Sigma,P,S) eine kontextfreie Grammatik in Chomsky-Normalform. Wir möchten eine kontextfreie Grammatik G=(V,Σ,P,S)G'=(V',\Sigma,P',S') konstruieren, sodass L(G)=Del(L(G))L(G')=\Del(L(G)) gilt. Hierzu setzen wir
V:=V{XabXV}{XaXV}{XbXV}V':= V\cup \{X_{ab}\mid X\in V\}\cup \{X_a\mid X\in V\}\cup \{X_b\mid X\in V\}
wobei Xab,Xa,XbVX_{ab},X_a,X_b\notin V für alle XVX\in V. Definieren Sie nun PP' und SS', sodass
1. LG(X)=LG(X)L_{G'}(X)=L_G(X)
2. LG(Xab)=Del(LG(X))L_{G'}(X_{ab})=\Del(L_G(X))
3. LG(Xa)={wΣwaLG(X)}L_{G'}(X_{a})=\{w\in\Sigma^*\mid wa\in L_G(X)\}
4. LG(Xb)={wΣbwLG(X)}L_{G'}(X_{b})=\{w\in\Sigma^*\mid bw\in L_G(X)\}
für alle XVX\in V gilt. Geben Sie die Produktionen PP' präzise an; vermeiden Sie unstrukturierten Fließtext.

Hinweis: GG ist in CNF, hat also keine ε\varepsilon-Produktionen. GG' muss nicht in CNF sein.
Startsymbol S:=SabS':=S_{ab}  

Produktionen PP':

1.  Original‑Produktionen (beibehalten)  
XV,  XYZPLongrightarrowXYZP
\forall X\in V,\;X\rightarrow YZ\in P\quad\Longrightarrow\quad X\rightarrow YZ\in P' 

XV,  XaPLongrightarrowXaP
\forall X\in V,\;X\rightarrow a\in P\quad\Longrightarrow\quad X\rightarrow a\in P' 


2.  Hilfs‑Nichtterminal XabX_{ab} – Entfernt genau ein Vorkommen von abab  
XabYabZXabYZabXabYaZbfu¨r jede Produktion XYZP
\begin{aligned}
X_{ab}&\rightarrow Y_{ab}\,Z \\
X_{ab}&\rightarrow Y\,Z_{ab} \\
X_{ab}&\rightarrow Y_{a}\,Z_{b}
\end{aligned}
\qquad\text{für jede Produktion }X\rightarrow YZ\in P


3.  Hilfs‑Nichtterminal XaX_{a} – Wörter, die durch Anhängen von aa zu LG(X)L_G(X) führen  
XaYaZXaYZafu¨r jede Produktion XYZP
\begin{aligned}
X_{a}&\rightarrow Y_{a}\,Z \\
X_{a}&\rightarrow Y\,Z_{a}
\end{aligned}
\qquad\text{für jede Produktion }X\rightarrow YZ\in P


Zusatz für terminale Produktionen:  
XaP  Longrightarrow  XaεXbP  Longrightarrow  Xbε
\begin{aligned}
X\rightarrow a &\in P \;\Longrightarrow\; X_{a}\rightarrow \varepsilon \\
X\rightarrow b &\in P \;\Longrightarrow\; X_{b}\rightarrow \varepsilon
\end{aligned}


4.  Hilfs‑Nichtterminal XbX_{b} – Wörter, die durch Voranstellen von bb zu LG(X)L_G(X) führen  
XbYbZXbYZbfu¨r jede Produktion XYZP
\begin{aligned}
X_{b}&\rightarrow Y_{b}\,Z \\
X_{b}&\rightarrow Y\,Z_{b}
\end{aligned}
\qquad\text{für jede Produktion }X\rightarrow YZ\in P


Zusatz für terminale Produktionen:  
XaP  Longrightarrow  Xb hat keine neue ProduktionXbP  Longrightarrow  Xbε
\begin{aligned}
X\rightarrow a &\in P \;\Longrightarrow\; X_{b}\text{ hat keine neue Produktion} \\
X\rightarrow b &\in P \;\Longrightarrow\; X_{b}\rightarrow \varepsilon
\end{aligned}


Damit gelten für alle XVX\in V:

LG(X)=LG(X)LG(Xab)=Del(LG(X))LG(Xa)={wwaLG(X)}LG(Xb)={wbwLG(X)}
\begin{aligned}
L_{G'}(X)      &= L_G(X)\\
L_{G'}(X_{ab}) &= \Del\bigl(L_G(X)\bigr)\\
L_{G'}(X_{a})  &= \{w\mid wa\in L_G(X)\}\\
L_{G'}(X_{b})  &= \{w\mid bw\in L_G(X)\}
\end{aligned}


und das Startsymbol SabS_{ab} erzeugt genau Del ⁣(L(G))\Del\!\bigl(L(G)\bigr).

Subproblem d (1.0/2.0P)

Wenden Sie Ihre Konstruktion auf das Beispiel G:=({S,A},{a,b},P,S)G:=(\{S,A\},\{a,b\},P,S) an, wobei PP gegeben ist durch:
SSAaAabS\to SA\mid a\qquad A\to a\mid b
Hinweis: Falls ein Nichtterminal nicht auf der linken Seite einer Produktion vorkommt, lassen Sie das entsprechende Feld leer.
Startsymbol S:=SabS':=S_{ab}  
Produktionen PP':
SSAaS\rightarrow SA\mid a
SabSabASAabSaAbS_{ab}\rightarrow S_{ab}A\mid SA_{ab}\mid S_{a}A_{b}
SaSaASAaεS_a\rightarrow S_{a}A\mid SA_{a}\mid \varepsilon
SbSbASAbS_b\rightarrow S_{b}A\mid SA_{b}
AabA\rightarrow a\mid b
AabA_{ab}\rightarrow 
AaεA_a\rightarrow \varepsilon
AbεA_b\rightarrow \varepsilon
2 mistakes

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P)

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
LL ist entscheidbarL\overline{L} ist entscheidbarLL ist semi-entscheidbar

Subproblem b (2.0/2.0P)

Seien L1,L2ΣL_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
L1L2L_1\cap L_2L1L2L_1\setminus L_2L1L2L_1L_2

Subproblem c (0.0/2.0P)

Sei L{0}L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:NNf:\N\rightarrow\N sind berechenbar?
f(n):=LΣnf(n):=|L\cap \Sigma^n|f(n):=min{kN:0kL}f(n):=\min\{k\in\N: 0^k\in L\}f(n):=1f(n):=1, falls 0nL0^n\in L, sonst f(n):=0f(n):=0
wrong answer for choice (1)

Subproblem d (2.0/2.0P)

Seien A,BΣA,B\subseteq\Sigma^* Sprachen mit ApSATpBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
ANPA\in\NPBNPB\in\NPBB ist NP-hartApBA\le_p B

Subproblem e (0.0/2.0P)

Sei LΣ{#}ΣL\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass LPL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,vΣu,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
LL{uvΣ:u#vL}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}{uvΣ:u#vLu=v}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}
wrong answer for choice (1)

Subproblem f (4.0/4.0P)

Sei LNPL\in\NP. Zeigen oder widerlegen Sie: LNPL^*\in\NP.
Ja, Beweis:Nein, Gegenbeispiel:
Beweis, dass LNPL^* \in \NP für jedes LNPL\in\NP

Sei VV ein polynomieller Verifizierer für LL.  
Für ein Wort wΣw\in\Sigma^* der Länge nn konstruieren wir einen Verifizierer VV^{*} für LL^{*} wie folgt.

Zertifikat.  
Das Zertifikat besteht aus  

1. einer Folge von Trennpositionen 0=i0<i1<i2<<ik=n0 = i_0 < i_1 < i_2 < \dots < i_k = n (wobei knk\le n), die die Zerlegung   
   w=w1w2wk,\qquwj=w[ij1+1 .. ij]w = w_1 w_2 \dots w_k,\qqu w_j = w[i_{j-1}+1\ ..\ i_j]  
   definiert, und  

2. für jedes Teilwort wjw_j ein Zertifikat cjc_j für VV, das beweist, dass wjLw_j\in LDa knk\le n und jedes cjc_j nur polynomielle Länge in wj|w_j| (also n\le n) besitzt, hat das gesamte Zertifikat Gesamtlänge  
O(n)Trennpositionen+kpoly(n)cj  =  O ⁣(npoly(n))=poly(n).
\underbrace{O(n)}_{\text{Trennpositionen}} + \underbrace{k\cdot \operatorname{poly}(n)}_{\sum |c_j|} \;=\; O\!\bigl(n\cdot\operatorname{poly}(n)\bigr)=\operatorname{poly}(n).


Verifikation.  
Der Verifizierer VV^{*} prüft in polynomialer Zeit:

1. dass die angegebenen Trennpositionen tatsächlich eine Zerlegung von ww ergeben,
2. für jedes j=1,,kj=1,\dots,k, dass VV das Teilwort wjw_j zusammen mit dem zugehörigen Zertifikat cjc_j akzeptiert.

Jede einzelne Ausführung von VV benötigt Zeit poly(wj)poly(n)\operatorname{poly}(|w_j|)\le\operatorname{poly}(n), also insgesamt  
kpoly(n)npoly(n)=poly(n)
k\cdot\operatorname{poly}(n) \le n\cdot\operatorname{poly}(n)=\operatorname{poly}(n)

Zeit.

Damit existiert ein polynomieller Verifizierer für LL^{*}, also liegt LL^{*} in NP\NP.

LNP  Longrightarrow  LNP
\boxed{L\in\NP \;\Longrightarrow\; L^{*}\in\NP}


Damit ist die Aussage „LNPL^{*}\in\NP“ richtig.

Exercise 7: Reduktion

Nehmen Sie PNP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „ApBA\le_p B“ für  Entscheidungsprobleme A,BA, B. Wenn die Aussage gilt, dann müssen Sie (1) eine präzise definierte Reduktionsfunktion angeben und (2) die Reduktionsfunktion auf die gegebene Instanz von Problem AA anwenden. Die Korrektheit der Reduktion müssen Sie nur skizzieren. Wenn die Aussage nicht gilt, dann müssen Sie dies beweisen.

Subproblem a (4.0/4.0P)

Sei G=(V,E)G=(V, E) ein ungerichteter Graph. Ein Hamilton-Pfad von GG ist eine Permutation v1,,vnv_1,\dotsc,v_n der Knoten von VV mit {vi,vi+1}E\{v_i, v_{i+1}\} \in E für jedes i{1,...,n1}i \in \{1, ..., n-1\}. Ein Hamilton-Kreis von GG ist ein Hamilton-Pfad von GG, der zusätzlich {vn,v1}E\{v_n, v_1\} \in E erfüllt.

Sei HAMILTON-PFAD das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Pfad hat. Sei HAMILTON-KREIS das Entscheidungsproblem, ob ein gegebener ungerichteter Graph einen Hamilton-Kreis hat.

Aussage: HAMILTON-PFAD p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E
Die Aussage giltDie Aussage gilt nicht
**Reduktionsfunktion $f$ (Hamilton‑Pfad → Hamilton‑Kreis)**  

Eingabe: ein ungerichteter Graph $G=(V,E)$.  
Ausgabe: der Graph $G' = f(G) = (V\cup\{u\}, E')$, wobei  

\[
E' = E \;\cup\; \bigl\{\,\{u,v\}\mid v\in V\,\bigr\}.
\]

Der neue Knoten $u$ wird also zu allen ursprünglichen Knoten adjazent gemacht (ein *universeller* Knoten).

---

**Anwendung von $f$ auf die gegebene Instanz**

Ursprüngliche Knoten: $V=\{A,B,C,D,E\}$  

Ursprüngliche Kanten:  
\[
\{A,B\},\; \{A,C\},\; \{B,C\},\; \{C,D\},\; \{C,E\},\; \{D,E\}.
\]

Wir führen einen neuen Knoten $U$ ein und verbinden ihn mit allen vorhandenen Knoten:

\[
\{U,A\},\{U,B\},\{U,C\},\{U,D\},\{U,E\}.
\]

Damit ist das Ergebnis‑Graph $G' = (V\cup\{U\},E')$ mit  

Knoten: $A,B,C,D,E,U$  

Kanten:
\[
\begin{aligned}
& A\!-\!B,\; A\!-\!C,\; B\!-\!C,\; C\!-\!D,\; C\!-\!E,\; D\!-\!E,\\
& U\!-\!A,\; U\!-\!B,\; U\!-\!C,\; U\!-\!D,\; U\!-\!E.
\end{aligned}
\]

---

**Korrektheit (Skizze)**  

*„$\Rightarrow$“*:  
Angenommen $G$ besitzt einen Hamilton‑Pfad $v_1,\dots ,v_n$.  
Füge den neuen Knoten $u$ am Anfang und am Ende des ein:
\[
u, v_1, v_2,\dots ,v_n, u .
\]
Da $u$ zu jedem $v_i$ adjazent ist, bilden diese Knoten eine Hamilton‑Kreis in $G'$.

*„$\Leftarrow$“*:  
Angenommen $G'$ besitzt einen Hamilton‑Kreis.  
Da $u$ der einzige mit Grad $|V|$ ist, muss $u$ im Kreis genau zweimal vorkommen – unmittelbar vor und nach zwei Nachbarn $x,y\in V$.  
Entfernt man $u$ aus dem Kreis, bleibt ein Pfad $x,\dots ,y$ der alle ursprünglichen Knoten $V$ exakt einmal besucht; also ist das ein Hamilton‑Pfad in $G$.

Damit gilt $G$ hat einen Hamilton‑Pfad  ⇔  $f(G)$ hat einen Hamilton‑Kreis, also ist $f$ eine polynomialzeit‑berechenbare Reduktion.

∎

Subproblem b (3.0/3.0P)

Sei CFG-LEERHEIT das Entscheidungsproblem, ob eine gegebene kontextfreie Grammatik GG kein Wort erzeugt, also ob L(G)=L(G)=\emptyset gilt.

Aussage: 3KNF-SAT p\leq_p CFG-LEERHEIT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1¬x2x3)(¬x1x2x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
Die Aussage giltDie Aussage gilt nicht
**Beweis, dass die Reduktion nicht existieren kann (unter der Annahme \(P\neq NP\)).**

1. **Komplexität von CFG‑LEERHEIT**  
   Das Problem, zu entscheiden, ob die von einer kontextfreien Grammatik \(G\) erzeugte Sprache leer ist, kann in linearer Zeit gelöst werden (z.\;B. durch Berechnung der erreichbaren Nichtterminalsymbole). Damit liegt **CFG‑LEERHEIT in \(P\)**.

2. **Komplexität von 3‑KNF‑SAT**  
   Das Erfüllbarkeitsproblem für 3‑KNF‑Formeln ist **NP‑voll**. Insbesondere ist es **NP‑schwer**; jede Sprache in \(NP\) lässt sich in polynomieller Zeit auf 3‑KNF‑SAT reduzieren.

3. **Folgerung einer hypothetischen Reduktion**  
   Angenommen, es gäbe eine polynomialzeit‑many‑one‑Reduktion  
   \[
   f : \text{3KNF‑SAT} \longrightarrow \text{CFG‑LEERHEIT}.
   \]
   Dann könnte man für jede 3‑KNF‑Formel \(\varphi\) zunächst \(f(\varphi)\) in polynomialer Zeit konstruieren und anschließend das Ergebnis von CFG‑LEERHEIT in polynomialer Zeit entscheiden. Damit gäbe es ein deterministisches Polynomzeit‑Verfahren für 3‑KNF‑SAT, also **\( \text{3KNF‑SAT} \in P\)**.

4. **Widerspruch zur Annahme \(P\neq NP\)**  
   Da 3‑KNF‑SAT NP‑voll ist, würde \(\text{3KNF‑SAT} \in P\) die Inklusion \(NP \subseteq P\) implizieren, also \(P = NP\). Das steht im Widerspruch zur Voraussetzung \(P \neq NP\).

5. **Schluss**  
   Unter der Annahme \(P\neq NP\) **kann keine polynomialzeit‑Reduktion von 3‑KNF‑SAT auf CFG‑LEERHEIT existieren**. Folglich ist die Aussage **falsch**.

∎

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

Eingabe: Eine endliche Menge M={m1,...,mk}M=\{m_1, ..., m_k\} und eine Menge T={T1,...,Tn}T=\{T_1, ..., T_n\}  von Teilmengen von MM.

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge STS \subseteq T, sodass jedes Element von MM in genau einer der Teilmengen in SS vorkommt?

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
**Reduktionsfunktion $f$ (EXAKTE‑ÜBERDECKUNG → SAT)**  

*Eingabe:*  ein Paar \((M,T)\) mit  
\(M=\{m_1,\dots ,m_k\}\) und \(T=\{T_1,\dots ,T_n\}\)  (jede \(T_i\subseteq M\)).  

*Ausgabe:*  eine aussagenlogische Formel \(\Phi = f(M,T)\) in konjunktiver Normalform.

1. **Variablen.**  Für jedes Teilmengenelement \(T_i\) führen wir eine boolesche Variable \(x_i\) ein.  
   \(x_i = 1\) bedeutet, dass \(T_i\) in die gesuchte exakte Überdeckung aufgenommen wird.

2. **„mindestens‑ein‑Set‑für‑jedes‑Element“-Klauseln.**  
   Für jedes Element \(m\in M\) bilden wir die Klausel  
   \[
   C_m^{\;\text{at‑least}} \;=\; \bigvee_{i:\,m\in T_i} x_i .
   \]
   (Falls kein \(T_i\) das Element enthält, ist die Instanz sofort **nicht** lösbar – die Reduktion erzeugt die triviale unbefriedigbare Formel.)

3. **„höchstens‑ein‑Set‑für‑jedes‑Element“-Klauseln.**  
   Für jedes \(m\in M\) und jedes ungeordnete Paar \((i,j)\) mit \(i<j\) und \(m\in T_i\cap T_j\) fügen wir die Klausel  
   \[
   C_{m,i,j}^{\;\text{at‑most}} \;=\; \lnot x_i \;\lor\; \lnot x_j .
   \]
   Diese Klauseln verhindern, dass ein Element von zwei unterschiedlichen gewählten Teilmengen gedeckt wird.

4. **Gesamte Formel.**  
   \[
   \Phi \;=\; \bigwedge_{m\in M}\;C_m^{\;\text{at‑least}}
               \;\;\land\;\;
               \bigwedge_{m\in M}\;\bigwedge_{i<j,\;m\in T_i\cap T_j}\;C_{m,i,j}^{\;\text{at‑most}} .
   \]

Die Konstruktion ist eindeutig, benötigt nur das Durchsuchen aller Elemente von \(M\) und aller Mengen von \(T\) und erzeugt polynomial viele Klauseln (höchstens \(|M|\cdot n^2\)).  Damit ist \(f\) eine polynomialzeit‑many‑one‑Reduktion.

---

### Korrektheit (Skizze)

*→*   Angenommen, es gibt eine exakte Überdeckung \(S\subseteq T\).  
Setze \(x_i=1\) genau für die Mengen \(T_i\in S\) und \(x_i=0\) sonst.  
Für jedes \(m\in M\) ist wegen der Exaktheit genau ein \(T_i\in S\) mit \(m\in T_i\); damit erfüllt \(C_m^{\;\text{at‑least}}\) und alle „höchstens‑ein‑“‑Klauseln (da nie zwei gewählte Mengen dasselbe Element teilen).  Somit ist \(\Phi\) erfüllbar.

*←*   Angenommen, \(\Phi\) ist erfüllbar und sei \(\alpha\) eine erfüllende Belegung.  
Definiere \(S=\{\,T_i\mid \alpha(x_i)=1\,\}\).  
Die „at‑least“‑Klauseln garantieren, dass jedes Element \(m\) in mindestens einer Menge aus \(S\) vorkommt.  
Die „at‑most“‑Klauseln verhindern, dass ein Element in zwei verschiedenen Mengen aus \(S\) vorkommt.  
Also enthält jedes \(m\) genau eine Menge aus \(S\); das heißt, \(S\) ist eine exakte Überdeckung von \(M\).

Damit gilt: \((M,T)\) hat eine exakte Überdeckung  ⇔  \(\Phi\) ist erfüllbar.  Somit ist die Reduktion korrekt.

---

## Anwendung auf die gegebene Instanz

**Instanz von EXAKTE‑ÜBERDECKUNG**

\[
\begin{aligned}
M &= \{1,2,3,4\},\\[2pt]
T_1 &= \{1\},\\
T_2 &= \{1,3\},\\
T_3 &= \{1,2,3\},\\
T_4 &= \{2,4\},\\
T_5 &= \emptyset .
\end{aligned}
\]

Wir führen Variablen \(x_1,\dots ,x_5\) ein.

### Klauseln für jedes Element

*Element 1* (in \(T_1,T_2,T_3\)):  
\[
\begin{aligned}
C_1^{\text{at‑least}} &: \; (x_1 \lor x_2 \lor x_3)\\
C_{1,1,2}^{\text{at‑most}} &: \;lnot x_1 \lor \lnot x_2)\\
C_{1,1,3}^{\text{at‑most}} &: \; (\lnot x_1 \lor \lnot x_3)\\
C_{1,2,3}^{\text{at‑most}} &: \; (\lnot x_2 \lor \lnot x_3)
\end{aligned}
\]

*Element 2* (in \(T_3,T_4\)):  
\[
\begin{aligned}
C_2^{\text{at‑least}} &: \; (x_3 \lor x_4)\\
C_{2,3,4}^{\text{at‑most}} &: \; (\lnot x_3 \lor \lnot x_4)
\end{aligned}
\]

*Element 3* (in \(T_2,T_3\)):  
\[
\begin{aligned}
C_3^{\text{at‑least}} &: \; (x_2 \lor x_3)\\
C_{3,2,3}^{\text{at‑most}} &: \; (\lnot x_2 \lor \lnot x_3)
\end{aligned}
\]

*Element 4* (in \(T_4\) allein):  
\[
C_4^{\text{at‑least}} :\; (x_4)
\]
(keine „at‑most“‑Klauseln, weil nur ein Set das Element enthält).

\(T_5\) ist leer und erzeugt keine Klauseln.

### Gesamte CNF‑Formel \(\Phi\)

\[
\begin}
\Phi =\;& (x_1 \lor x_2 \lor x_3) \;\land\;
          (\lnot x_1 \lor \lnot x_2) \;\land\;
          (\lnot x_1 \lor \lnot x_3) \;\land\;
          (\lnot x_2 \lor \lnot x_3) \\[2pt]
        &\land\; (x_3 \lor x_4) \;\land\;
          (\lnot x_3 \lor \lnot x_4) \\[2pt]
        &\land\; (x_2 \lor x_3) \;\land\;
          (\lnot x_2 \lor \lnot x_3) \\[2pt]
        &\land\; (x_4).
\end{aligned}
\]

**Interpretation:**  
Die Belegung \(x_2 = 1,\; x_4 = 1\) und \(x_1 = x_3 = x_5 = 0\) erfüllt \(\Phi\).  
Sie entspricht genau der Auswahl der Teilmengen \(T_2=\{1,3\}\) und \(T_4=\{2,4\}\), die jedes Element aus \(M\) **einmal** und nur einmal abdecken – also einer exakten Überdeckung.

Damit ist die Reduktion auf die gegebene Instanz vollzogen. ∎

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (0.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
wrong answer for choice (0)
Beweis für Sprache 3:
Wir zeigen, dass die Sprache  

L={aibjck(i1    j=k)  i,j,k0}
L=\{a^{i}b^{j}c^{k}\mid (i\neq 1\;\vee\;j=k)\ \wedge\ i,j,k\ge 0\}


nicht regulär ist.  
Dazu benutzen wir die Abschluß‑Eigenschaften regulärer Sprachen und das bekannte Nicht‑Regularitäts­Resultat für  
K={abncnn0}.
K=\{ab^{n}c^{n}\mid n\ge 0\}.


---

### 1.  Komplement von LL

Das Komplement von LL (bezogen auf Σ\Sigma^{*}) ist  

L=ΣL={abjckjk}.
\overline{L}= \Sigma^{*}\setminus L
        = \{a\,b^{j}c^{k}\mid j\neq k\}.


Man erkenne, dass L\overline{L} bereits innerhalb der regulären Menge  

R=abc
R = a\,b^{*}c^{*}


liegt, also L=RL\overline{L}=R\cap\overline{L}.

---

### 2.  Annahme:  L\overline{L} wäre regulär

Angenommen, L\overline{L} wäre regulär.  
Da reguläre Sprachen unter Komplement und Schnitt mit regulären Sprachen abgeschlossen sind, würde dann auch

K=RL=R(ΣL)
K = R \setminus \overline{L}
    = R \cap (\Sigma^{*}\setminus\overline{L})


regulär sein.

Aber K={abncnn0}K = \{ab^{n}c^{n}\mid n\ge 0\} ist die klassische Beispiel­sprache, die nicht regulär ist (Pumping‑Lemma bzw. Myhill‑Nerode).  
Damit entsteht ein Widerspruch zur Annahme, dass L\overline{L} regulär ist.

---

### 3.  Schlussfolgerung

Der Widerspruch zeigt, dass L\overline{L} nicht regulär sein kann.  
Da die regulären Sprachen unter Komplement abgeschlossen sind, folgt daraus sofort, dass auch LL nicht regulär sein muss.

L ist nicht regula¨r
\boxed{L\ \text{ist nicht regulär}}


Damit ist Sprache 3 eine nicht‑reguläre Sprache, und wir haben den Beweis erbracht.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: bbab
2: -
3: babb

Subproblem c (0.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Wir zeigen, dass die Menge  
\[
L_1=\{w\in\{0,1\}^* \mid |L(M_w)|^2 = 25\}
      =\{w \mid |L(M_w)| = 5\}
\]
unentscheidbar ist, indem wir das bekannte **Leerheits‑Problem** für Turing‑maschinen  
\[
\text{EMP}=\{\langle M\rangle \mid L(M)=\varnothing\}
\]
auf sie reduzieren.

---

### 1.   Das Leerheits‑Problem ist unentscheidbar  
(standarder Satz, Beweis durch Reduktion vom Halte‑Problem).

### 2.   Konstruktion einer TM \(M'\) aus einer beliebigen TM \(M\)

Gegeben eine TM \(M\) (Kodierung \(w=\langle M\rangle\)).  
Wir bauen eine neue TM \(M'\) wie folgt:

*Fixierte Menge von fünf Strings*  
\[
S=\{0,1,00,01,10\}.
\]

\(M'\) arbeitet auf Eingabe \(x\):

1. Falls \(x\in S\) akzeptiere sofort.
2. Falls \(x = z\) (ein spezieller zusätzlicher String, z.B. \(z = 11\)), simuliere \(M\) auf **einem** festen Eingabewort (z.B. das leere Wort).  
   - Falls \(M\) mindestens ein Wort akzeptiert, akzeptiere \(z\).  
   - Andernfalls verwerfe \(z\).
3. Für jedes andere \(x\) verwerfe.

Damit gilt:

* Wenn \(L(M)=\varnothing\) akzeptiert \(M'\) **genau** die fünf Wörter aus \(S\).  
  \(|L(M')| = 5\).

* Wenn \(L(M)\neq\varnothing) akzeptiert \(M'\) die fünf Wörter aus \(S\) **und** zusätzlich \(z\).  
  \(|L(M')| = 6\) (oder sogar größer, falls man weitere Wörter zulassen würde – wichtig ist nur, dass die Größe ≠ 5 ist).

Die Konstruktion ist effektiv; es gibt eine totale, berechenbare Funktion  
\[
f:\{0,1\}^* \to \{0,1\}^*,\qquad f(w)=\langle M'\rangle .
\]

### 3.   Korrektheit der Reduktion

\[
w\in\text{EMP}\;\Longleftrightarrow\; |L(M_{f(w)})| = 5\;\Longleftrightarrow\; f(w)\in L_1 .
\]

Somit ist \(f\) eine many‑one‑Reduktion von EMP auf \(L_1\).

### 4.   Schluss

Da EMP unentscheidbar ist und EMP many‑one‑reduzierbar auf \(L_1\) ist, muss \(L_1\) ebenfalls unentscheidbar sein.  
Analog lässt sich derselbe Beweis für die Sprache mit \(|L(M_w)|^2 = 100\) (also \(|L(M_w)| = 10\)) führen; die Sprache mit \(|L(M_w)|^2 = 50\) ist dagegen leer und damit entscheidbar.

\[
\boxed{\text{Die unentscheidbaren Optionen sind }1\text{ und }3.}
\]

Beweis abgeschlossen.