Exam 2024_retake.txt — qwen/qwen3-235b-a22b-thinking-2507

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 3.0/3.0 1.0/3.0 14.0/16.0
2: DFA-Algorithmen 1.0/6.0 0.0/1.0 4.0/4.0 2.0/2.0 5.0/5.0 12.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 7.0/7.0 2.0/2.0 12.0/12.0
6: Quiz: Berechenbarkeit und Komplexität 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 4.0/4.0 14.0/14.0
7: Reduktion 4.0/4.0 3.0/3.0 7.0/7.0 14.0/14.0
8: Bonus 2.0/2.0 1.0/1.0 2.0/2.0 5.0/5.0
Exam total 95.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 L☒LLL=Σ∗LLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei L⊆Σ∗L \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
☒{uRv∣u,v∈L}\{u^R v \mid u, v \in L\}☐{uRu∣u∈L}\{u^R u \mid u \in L\}☐{uv∣u,v∈L∧∣u∣=∣v∣}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
☒S→SS∣aS \rightarrow SS \mid a☐S→Sa∣Sb∣εS \rightarrow Sa \mid Sb \mid \varepsilon☒S→TTT→aT∣bT∣a∣bS \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?
☐A∪B‾A \cup \overline{B}☒A‾∪B\overline{A} \cup B☒ABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
X≡a∗b∗aX∣abX \equiv a^*b^*aX \mid ab
Y≡(b∣a)a∗Y∣bbY∣ϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Z≡a∗(a∣b)ZZ \equiv a^*(a \mid b)Z
X=(a∗b∗a)∗abX=(a^*b^*a)^*ab
Y=(a+b)∗Y=(a+b)^*
Z=∅Z=\emptyset

Subproblem g (1.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2∈Qq_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 NFA☒Falsch, Beweis
Es gibt keinen reversiblen NFA für L((aa)∗(bb)∗)L((aa)^*(bb)^*).  

Beweis: Angenommen, es existiert ein reversibler NFA NN mit L(N)=LL(N) = L. Betrachte die Zeichenfolge s=aabb∈Ls = aabb \in L. Da NN reversibel ist, bilden die Übergänge für aa und bb jeweils ungerichtete Graphen. Für ss führen zwei aa-Übergänge von q0q_0 zu einem Zustand mit gerader aa-Anzahl (zurück zu einem Start-Zustand-ähnlichen Zustand), gefolgt von zwei bb-Übergängen. Aufgrund der Reversibilität gilt aber auch: Die Zeichenfolge t=bbaat = bbaa (eine Permutation von ss) würde dieselben Zustandswechsel auslösen, da bb-Übergänge die "Rückkehr" in den Zustand vor den bb-Eingaben ermöglichen. Somit akzeptiert NN ebenfalls t∉Lt \notin L, was ein Widerspruch ist.  
Allgemein sind Sprachen, die auf symbolweiser Reihenfolge basieren (wie aa's vor bb's), nicht durch reversible NFAs erkennbar, da Reversibilität die Eingabezeichen vertauschen kann, ohne die Erkennung zu beeinträchtigen.

Exercise 2: DFA-Algorithmen


Subproblem a (1.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, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, a -> q3
    q2, b -> q5
    q3, a -> q6
    q3, b -> q4
    q7, a -> q7
    q7, b -> q7
    q5, a -> q7
    q5, b -> q5
    q6, a -> q3
    q6, b -> q7
    q4, a -> q4
    q4, b -> q4
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 3
    q4: \emptyset
    q5: 0, 1, 2, 3
    q6: 1, 2
    q7: 1, 2, 3
7 wrong transitions (-4P)
wrong state sets for [3, 5] (-1P)

Subproblem b (0.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
☐Ja☒Nein
Nein, da es äquivalente Zustände gibt. Beispielsweise sind q2 und q6 äquivalent, da sie für alle Eingaben in dieselben Zustandsklassen übergehen (z.B. führt 'a' beide nach q3 und 'b' nach {q5,q7}). Ebenso können q5 und q7 zusammengefasst werden, da sie identisches Akzeptanzverhalten zeigen.

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 (5.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:N→Nf:\N\rightarrow\N, sodass es einen DFA M′M' 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 M′M' zu berechnen uns argumentieren Sie, wieso M′M' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:
Um M′M' zu berechnen, führen wir eine modifizierte Potenzmengenkonstruktion durch. Zuerst berechnen wir für jeden Zustand qq von MM die Menge reachc(q)\text{reach}_c(q), bestehend aus allen Zuständen, die von qq aus durch beliebig viele cc-Übergänge erreichbar sind. Da MM ein DFA ist, bilden die cc-Übergänge deterministische Pfade, möglicherweise mit einer Schleife.

Der DFA M′M' wird wie folgt konstruiert:
- Zustände: Alle Teilmengen der Zustände von MM, also P(Q)\mathcal{P}(Q).
- Startzustand: reachc(q0)\text{reach}_c(q_0), wobei q0q_0 der Startzustand von MM ist.
- Übergänge: Für eine Teilmenge S⊆QS \subseteq Q und σ∈{a,b}\sigma \in \{a,b\} ist δ′(S,σ)=⋃q∈Sreachc(δ(q,σ))\delta'(S, \sigma) = \bigcup_{q \in S} \text{reach}_c(\delta(q, \sigma)).
- Finalzustände: Alle Teilmengen SS, die mindestens einen Finalzustand von MM enthalten.

Die Anzahl der Zustände in M′M' ist durch 2n2^n beschränkt, da es maximal 2n2^n Teilmengen der nn Zustände von MM gibt. Dies ist im Worst Case auch notwendig, z.B. wenn alle cc-Übergänge Selbstschleifen sind (reachc(q)={q}\text{reach}_c(q) = \{q\}), sodass die Konstruktion äquivalent zur Umkehrung des DFA ist, die bekanntermaßen 2n2^n Zustände benötigen kann.

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):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}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,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

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):=a∣(0a)∣(a0)\Null(a) := a \mid (0a) \mid (a0)
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2∣r1Null(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(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(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 u1v∈L(r)u1v\in L(r) gilt, dass u∈L(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 u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
Wir nehmen an, dass die Aussage für r1r_1 und r2r_2 gilt, also:
- Für alle u1,v1∈Σ∗u_1,v_1\in\Sigma^* mit u11v1∈L(r1)u_1 1 v_1\in L(r_1) gilt u1∈L(Cut(r1))u_1\in L(\Cut(r_1)).
- Für alle u2,v2∈Σ∗u_2,v_2\in\Sigma^* mit u21v2∈L(r2)u_2 1 v_2\in L(r_2) gilt u2∈L(Cut(r2))u_2\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1v∈L(r1r2)u 1 v \in L(r_1 r_2) mit u,v∈Σ∗u, v \in \Sigma^*. Dann gibt es w1,w2w_1, w_2 mit w1w2=u1vw_1 w_2 = u 1 v, w1∈L(r1)w_1 \in L(r_1), w2∈L(r2)w_2 \in L(r_2).

Wir unterscheiden zwei Fälle:
- Fall 1: Der Buchstabe "1" liegt in w1w_1, d.h. w1=u11v1w_1 = u_1 1 v_1 für einige u1,v1∈Σ∗u_1, v_1 \in \Sigma^*, und u=u1u = u_1, v1w2=1vv_1 w_2 = 1 v.
  Dann ist u11v1∈L(r1)u_1 1 v_1 \in L(r_1). Nach Induktionshypothese für r1r_1 folgt u1∈L(Cut(r1))u_1 \in L(\Cut(r_1)) (IH1). 
  Da Cut(r1r2)=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) = \Cut(r_1) \mid r_1 \Cut(r_2), ist u=u1∈L(Cut(r1))⊆L(Cut(r1r2))u = u_1 \in L(\Cut(r_1)) \subseteq L(\Cut(r_1 r_2)).

- Fall 2: Der Buchstabe "1" liegt in w2w_2, d.h. w2=u21v2w_2 = u_2 1 v_2 für einige u2,v2∈Σ∗u_2, v_2 \in \Sigma^*, und u=w1u2u = w_1 u_2, v2=vv_2 = v.
  Dann ist u21v2∈L(r2)u_2 1 v_2 \in L(r_2). Nach Induktionshypothese für r2r_2 folgt u2∈L(Cut(r2))u_2 \in L(\Cut(r_2)) (IH2).
  Da w1∈L(r1)w_1 \in L(r_1) und u2∈L(Cut(r2))u_2 \in L(\Cut(r_2)), ist w1u2∈L(r1Cut(r2))w_1 u_2 \in L(r_1 \Cut(r_2)).
  Da Cut(r1r2)=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) = \Cut(r_1) \mid r_1 \Cut(r_2), ist u=w1u2∈L(r1Cut(r2))⊆L(Cut(r1r2))u = w_1 u_2 \in L(r_1 \Cut(r_2)) \subseteq L(\Cut(r_1 r_2)).

In beiden Fällen gilt u∈L(Cut(r1r2))u \in L(\Cut(r_1 r_2)), was zu zeigen war.

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 X∈VX\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 G′G' 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 G′G' als G^\hat{G} ohne die ϵ\epsilon-Produktionen. Denn diese sind nun überflüssig.

Wir nennen A→BA \rightarrow B eine Kettenproduktion.
\begin{Lemma}
Zu jeder CFG G=(V,Σ,P,S)G = (V,\Sigma,P,S) kann man eine CFG G′G' 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{A→BA \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 G′G' 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 Aa→aA_a\rightarrow a zu PP hinzu.
\item Ersetze jede Produktion der Form
A→B1B2⋯Bk(k≥3)A\rightarrow B_1B_2 \cdots B_k (k \geq 3)
durch
A→B1C2, C2→B2C3,...,Ck−1→Bk−1BkA \rightarrow B_1C_2,\ C_2 \rightarrow B_2C_3, ..., C_{k-1} \rightarrow B_{k-1}B_k 
wobei C2,...,Ck−1C_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:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣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 Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.
S→AaX∣XAa∣AaAbS \rightarrow A_aX \mid XA_a \mid A_aA_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_bXX
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \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 Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.
S→A∣BC∣εS \rightarrow A \mid BC \mid \varepsilon
A→SD∣aA \rightarrow SD \mid a
B→AS∣bB \rightarrow AS \mid b
C→AAC \rightarrow AA
D→AED \rightarrow AE
E→BBE \rightarrow BB

Subproblem c (3.0/3.0P)

Entfernen von ε\varepsilon-Produktionen. Die CFG GcG_c ist gegeben durch folgende Produktionen:
S→AB∣DES \rightarrow AB \mid DE
A→AB∣a∣εA \rightarrow AB \mid a \mid \varepsilon
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BSD \rightarrow BC \mid BS
E→SS∣CAE \rightarrow SS \mid CA
Führen Sie den dritten Schritt des Algorithmus zur Überführung in CNF aus. Geben Sie die Produktionen einer CFG Gc′G'_c an, so dass L(Gc)=L(Gc′)L(G_c) = L(G'_c) und Gc′G'_c Bedingungen (1), (2) und (3) erfüllt.
S→AB∣DE∣B∣DS \rightarrow AB \mid DE \mid B \mid D
A→AB∣B∣aA \rightarrow AB \mid B \mid a
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣B∣BSD \rightarrow BC \mid B \mid BS
E→SS∣CA∣C∣AE \rightarrow SS \mid CA \mid C \mid A

Subproblem d (3.0/3.0P)

Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \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 Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.
S→a∣b∣BA∣SC∣AAS \rightarrow a \mid b \mid BA \mid SC \mid AA
A→a∣AAA \rightarrow a \mid AA
B→a∣b∣SC∣AAB \rightarrow a \mid b \mid SC \mid AA
C→SS∣a∣b∣SC∣AAC \rightarrow SS \mid a \mid b \mid SC \mid AA

Subproblem e (2.0/3.0P)

Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣ε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):={vw∣v,w∈Σ∗∧vabw∈L}\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})={ε,abba,baba}\Del(\{abbaba,baa,ab,a,b\}) = \{\varepsilon, abba, baba\}

Subproblem b (2.0/2.0P)

Wir definieren DelTwo(L):={uvw∣u,v,w∈Σ∗∧uabvabw∈L}\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).
☐Wahr☒Falsch
Betrachte die endliche Sprache L={aabb}L = \{aabb\}.

- Del(L)\Del(L) enthält alle Wörter, die durch einmaliges Entfernen von abab aus aabbaabb entstehen.  
  In aabbaabb kommt abab genau an einer Position vor (zwischen den Zeichen an Position 1 und 2).  
  Entfernt man abab, bleibt a⋅b=aba \cdot b = ab. Also: Del(L)={ab}\Del(L) = \{ab\}.  

- Del(Del(L))=Del({ab})\Del(\Del(L)) = \Del(\{ab\}).  
  Entfernt man abab aus abab, erhält man ε\varepsilon. Also: Del(Del(L))={ε}\Del(\Del(L)) = \{\varepsilon\}.  

- DelTwo(L)\DelTwo(L) enthält alle Wörter uvwuvw, für die uabvabw∈Luabvabw \in L gilt.  
  Aber aabbaabb enthält nur ein Vorkommen von abab, sodass keine zwei abab-Teilwörter entfernt werden können.  
  Daher: DelTwo(L)=∅\DelTwo(L) = \emptyset.  

Da {ε}≠∅\{\varepsilon\} \neq \emptyset, gilt Del(Del(L))≠DelTwo(L)\Del(\Del(L)) \neq \DelTwo(L). Dies widerlegt die Aussage für die endliche Sprache L={aabb}L = \{aabb\}.

Subproblem c (7.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∪{Xab∣X∈V}∪{Xa∣X∈V}∪{Xb∣X∈V}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,Xb∉VX_{ab},X_a,X_b\notin V für alle X∈VX\in V. Definieren Sie nun P′P' und S′S', 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∈Σ∗∣wa∈LG(X)}L_{G'}(X_{a})=\{w\in\Sigma^*\mid wa\in L_G(X)\}
4. LG′(Xb)={w∈Σ∗∣bw∈LG(X)}L_{G'}(X_{b})=\{w\in\Sigma^*\mid bw\in L_G(X)\}
für alle X∈VX\in V gilt. Geben Sie die Produktionen P′P' präzise an; vermeiden Sie unstrukturierten Fließtext.

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

Produktionen P′P':
P′=P∪{Xa→ε∣X→a∈P}∪{Xb→ε∣X→b∈P}∪{Xa→YZa∣X→YZ∈P}∪{Xb→YbZ∣X→YZ∈P}∪{Xab→YabZ,Xab→YZab,Xab→YaZb∣X→YZ∈P}
P' = P \cup \{ X_a \to \varepsilon \mid X \to a \in P \} \cup \{ X_b \to \varepsilon \mid X \to b \in P \} \cup \{ X_a \to Y Z_a \mid X \to YZ \in P \} \cup \{ X_b \to Y_b Z \mid X \to YZ \in P \} \cup \{ X_{ab} \to Y_{ab} Z,  X_{ab} \to Y Z_{ab},  X_{ab} \to Y_a Z_b \mid X \to YZ \in P \}

Subproblem d (2.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:
S→SA∣aA→a∣bS\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 P′P':
S→SA∣aS\rightarrow SA\mid a
Sab→SabA∣SAab∣SaAbS_{ab}\rightarrow S_{ab}A\mid SA_{ab}\mid S_aA_b
Sa→SAa∣εS_a\rightarrow SA_a\mid \varepsilon
Sb→SbAS_b\rightarrow S_bA
A→a∣bA\rightarrow a\mid b
Aab→A_{ab}\rightarrow 
Aa→εA_a\rightarrow \varepsilon
Ab→εA_b\rightarrow \varepsilon
0 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 entscheidbar☒L‾\overline{L} ist entscheidbar☒LL 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?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P)

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P)

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (2.0/2.0P)

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\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☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P)

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel:
Ja. Sei L∈NPL \in \NP mit einem polynomiellen Verifizierer VLV_L. Für w∈Σ∗w \in \Sigma^* ist w∈L∗w \in L^* genau dann, wenn es eine Zerlegung w=x1x2⋯xkw = x_1x_2\cdots x_k mit k≥0k \geq 0 und xi∈Lx_i \in L gibt. Das Zertifikat für ww besteht aus den Teilungsstellen 0=i0<i1<⋯<ik=∣w∣0 = i_0 < i_1 < \cdots < i_k = |w| sowie Zertifikaten c1,…,ckc_1, \dots, c_k für xj=w[ij−1..ij]∈Lx_j = w[i_{j-1}..i_j] \in L. Der Verifizierer für L∗L^* überprüft:
1. Die Gültigkeit der Teilungsstellen (d. h. i0=0i_0=0, ik=∣w∣i_k=|w|, ij>ij−1i_j > i_{j-1}).
2. Für jedes jj, dass VL(xj,cj)V_L(x_j, c_j) akzeptiert.

Da k≤∣w∣k \leq |w| und jedes cjc_j polynomiell in ∣xj∣|x_j| ist, ist die Zertifikatlänge polynomiell in ∣w∣|w|. Jeder Verifikationsschritt läuft in polynomieller Zeit, also ist der Gesamtverifizierer polynomiell zeitbeschränkt. Somit gilt L∗∈NPL^* \in \NP.

Exercise 7: Reduktion

Nehmen Sie P≠NP\P\ne\NP an. Entscheiden Sie unter dieser Annahme, welche der folgenden Aussagen gelten. Die Aussagen sind von der Gestalt „A≤pBA\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,...,n−1}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 gilt☐Die Aussage gilt nicht
Reduktionsfunktion: Sei G=(V,E)G = (V, E) eine Instanz von HAMILTON-PFAD. Definiere die Reduktionsfunktion ff, die GG auf einen neuen Graphen G′=(V′,E′)G' = (V', E') abbildet, wobei:
- V′=V∪{u}V' = V \cup \{u\} (uu ist ein neu hinzugefügter Knoten),
- E′=E∪{{u,v}∣v∈V}E' = E \cup \{\{u, v\} \mid v \in V\}.

Anwendung auf die gegebene Instanz:  
Gegebener Graph GG mit Knoten {A,B,C,D,E}\{A, B, C, D, E\} und Kanten {A–B,A–C,B–C,C–D,C–E,D–E}\{A\text{--}B, A\text{--}C, B\text{--}C, C\text{--}D, C\text{--}E, D\text{--}E\}.  
Der transformierte Graph G′=f(G)G' = f(G) hat:
- Knoten: A,B,C,D,E,uA, B, C, D, E, u,
- Kanten: Alle Kanten von GG und zusätzliche Kanten {u–A,u–B,u–C,u–D,u–E}\{u\text{--}A, u\text{--}B, u\text{--}C, u\text{--}D, u\text{--}E\}.

Korrektheit (Skizze):  
- Hinrichtung: Besitzt GG einen Hamilton-Pfad v1–…–vnv_1\text{--}\dots\text{--}v_n, so bildet u–v1–…–vn–uu\text{--}v_1\text{--}\dots\text{--}v_n\text{--}u einen Hamilton-Kreis in G′G', da uu mit allen Knoten verbunden ist.
- Rückrichtung: Enthält G′G' einen Hamilton-Kreis, so muss dieser uu enthalten. Durch Entfernen von uu und Verbinden seiner Nachbarn entsteht ein Hamilton-Pfad in GG.
- Die Reduktion ist offensichtlich in polynomieller Zeit berechenbar, da sie lediglich einen Knoten und nn Kanten hinzufügt.

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∨¬x2∨x3)∧(¬x1∨x2∨x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)
☐Die Aussage gilt☒Die Aussage gilt nicht
Beweis, dass die Aussage nicht gilt:  
Unter der Annahme P≠NP\P \ne \NP gilt, dass CFG-LEERHEIT in P\P liegt. Das Problem CFG-LEERHEIT ist effizient lösbar: Ein Algorithmus mit Laufzeit O(∣G∣)\mathcal{O}(|G|) prüft, ob das Startsymbol der Grammatik GG terminale Zeichen ableiten kann (durch Markieren von Symbolen, die zu Terminalen reduzieren). Da 3KNF-SAT3\text{KNF-SAT} NP\NP-vollständig ist, würde eine polynomielle Reduktion 3KNF-SAT≤pCFG-LEERHEIT3\text{KNF-SAT} \leq_p \text{CFG-LEERHEIT} implizieren, dass 3KNF-SAT3\text{KNF-SAT} in P\P liegt. Dies widerspricht P≠NP\P \ne \NP. Somit kann die Reduktion nicht existieren.

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 S⊆TS \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\},
T5≔∅T_5\coloneqq\emptyset.
☒Die Aussage gilt☐Die Aussage gilt nicht
**Reduktionsfunktion:**  
Sei $(M, T)$ eine Instanz von EXAKTE-ÜBERDECKUNG mit $M = \{m_1, \dotsc, m_k\}$ und $T = \{T_1, \dotsc, T_n\}$. Definiere eine SAT-Instanz mit Variablen $x_1, \dotsc, x_n$, wobei $x_i$ angibt, ob $T_i \in S$ gilt. Für jedes $m_j \in M$ sei $I_j = \{i \mid m_j \in T_i\}$. Die SAT-Formel besteht aus:  
1. **„Mindestens ein“-Klauseln**: $\bigvee_{i \in I_j} x_i$ für jedes $m_j \in M$,  
2. **„Höchstens ein“-Klauseln**: $(\neg x_i \vee \neg x_{i'})$ für alle $i < i' \in I_j$ und jedes $m_j \in M$.  

**Anwendung auf die gegebene Instanz:**  
$M = \{1,2,3,4\}$, $T = \{T_1, T_2, T_3, T_4, T_5\}$ mit $T_1 = \{1\}$, $T_2 = \{1,3\}$, $T_3 = \{1,2,3\}$, $T_4 = \{2,4\}$, $T_5 = \emptyset$.  
- Variablen: $x_1, x_2, x_3, x_4, x_5$.  
- **Klauseln**:  
  - Für $m=1$ ($I_1 = \{1,2,3\}$):  
    $(x_1 \vee x_2 \vee x_3)$,  
    $(\neg x_1 \vee \neg x_2)$, $(\neg x_1 \vee \neg x_3)$, $(\neg x_2 \vee \neg x_3)$.  
  - Für $m=2$ ($I_2 = \{3,4\}$):  
    $(x_3 \vee x_4)$, $(\neg x_3 \vee \neg x_4)$.  
  - Für $m=3$ ($I_3 = \{2,3\}$):  
    $(x_2 \vee x_3)$, $(\neg x_2 \vee \neg x_3)$.  
  - Für $m=4$ ($I_4 = \{4\}$):  
    $(x_4)$.  
  - $T_5$ enthält kein Element, also keine Klauseln für $x_5$.  
- Resultierende CNF:  
\[
(x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge \\
(x_3 \vee x_4) \wedge (\neg x_3 \vee \neg x_4) \wedge (x_2 \vee x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge (x_4).
\]

**Korrektheit (Skizze):**  
- **Hinrichtung:** Eine exakte Überdeckung $S \subseteq T$ definiert eine erfüllende Belegung mit $x_i = 1 \iff T_i \in S$. Die Klauseln garantieren, dass jedes Element *genau* einmal abgedeckt wird.  
- **Rückrichtung:** Eine erfüllende Belegung induziert ein $S = \{T_i \mid x_i = 1\}$, das eine exakte Überdeckung ist, da die Klauseln die Disjunktheit und Vollständigkeit der Abdeckung erzwingen.  
- Die Reduktion ist polynomiell, da die Anzahl der Klauseln $\mathcal{O}(k \cdot n^2)$ ist ($k = |M|$, $n = |T|$).

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.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∈Σ∗:∣w∣aba≠∣w∣a}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}☐({w∈Σ∗:w=wR})∗\big(\{w\in\Sigma^*:w=w^R\}\big)^*☒{aibjck:(i≠1∨j=k)∧i,j,k≥0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:
Sei angenommen, die Sprache L3={aibjck:(i≠1∨j=k)∧i,j,k≥0}L_3 = \{a^ib^jc^k: (i\ne 1\vee j=k)\wedge i,j,k\ge0\} ist regulär. Betrachte die reguläre Sprache R=ab∗c∗R = a b^* c^*. Der Schnitt L3∩RL_3 \cap R besteht aus allen Strings der Form abjcka b^j c^k, wobei i=1i = 1 gilt. Die Bedingung (i≠1∨j=k)(i \neq 1 \vee j = k) vereinfacht sich für i=1i = 1 zu j=kj = k. Somit ist L3∩R={abjcj∣j≥0}L_3 \cap R = \{a b^j c^j \mid j \geq 0\}. Diese Sprache ist nicht regulär, da {bjcj∣j≥0}\{b^j c^j \mid j \geq 0\} mit dem Pumping-Lemma als nicht regulär nachweisbar ist (z.B. Wähle s=bpcps = b^p c^p; jede Zerlegung s=xyzs = xyz mit ∣xy∣≤p|xy| \leq p führt bei Pumpen zu einem String außerhalb der Sprache). Da reguläre Sprachen unter Schnitt abgeschlossen sind, muss L3∩RL_3 \cap R regulär sein, wenn L3L_3 regulär wäre. Dies ist ein Widerspruch. Folglich ist L3L_3 nicht regulär.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt L≠LRL\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(b∗a∗b)L(b^*a^*b)☐{w∈Σ∗:w≠wR}\{w\in\Sigma^*:w\ne w^R\}☒{uavv:u,v∈Σ∗}\{uavv:u,v\in\Sigma^*\}
1: ab
2: -
3: aaab

Subproblem c (2.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:
Angenommen, die Sprache L1={w∈Σ∗:∣L(Mw)∣2=25}L_1 = \{w \in \Sigma^* : |L(M_w)|^2 = 25\} ist entscheidbar. Dies ist äquivalent zu ∣L(Mw)∣=5|L(M_w)| = 5, da ∣L(Mw)∣|L(M_w)| eine nichtnegative ganze Zahl oder unendlich ist und 52=255^2 = 25. Die Bedingung ∣L(Mw)∣=5|L(M_w)| = 5 definiert eine nichttriviale semantische Eigenschaft der Sprachen: Es gibt Turingmaschinen, deren Sprachen genau 5 Wörter enthalten (z.B. MM mit L(M)={ϵ,0,1,00,01}L(M) = \{\epsilon, 0, 1, 00, 01\}), und andere, die diese Eigenschaft nicht erfüllen (z.B. eine Maschine mit leerer Sprache). Nach dem Satz von Rice ist jede nichttriviale semantische Eigenschaft unentscheidbar. Somit ist L1L_1 unentscheidbar.