Exam 2024_retake.txt — google/gemini-2.5-pro

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 3.0/3.0 16.0/16.0
2: DFA-Algorithmen 6.0/6.0 1.0/1.0 4.0/4.0 2.0/2.0 5.0/5.0 18.0/18.0
3: Rekursive Funktionen 1.0/1.0 6.0/6.0 6.0/6.0 13.0/13.0
4: CFG-Algorithmen 2.0/2.0 2.0/2.0 3.0/3.0 3.0/3.0 3.0/3.0 13.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 0.0/1.0 2.0/2.0 4.0/5.0
Exam total 104.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 (3.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)abb)Y=((a|b)a^*|bb)^*
Z=Z=\emptyset

Subproblem g (3.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
Nein, es gibt keinen solchen reversiblen NFA.

Beweis durch Widerspruch:

Angenommen, es existiert ein reversibler NFA N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F), der die Sprache L=L((aa)(bb))L = L((aa)^*(bb)^*) akzeptiert.

1.  Da das leere Wort ε\varepsilon in LL ist, muss der Startzustand q0q_0 ein Endzustand sein, d.h. q0Fq_0 \in F.

2.  Das Wort aaaa ist in LL. Also muss es einen Pfad q0aq1aq2q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_2 für Zustände q1,q2Qq_1, q_2 \in Q geben, sodass q2q_2 ein Endzustand ist (q2Fq_2 \in F).

3.  Das Wort aabbaabb ist in LL. Da der Pfad für aaaa in q2q_2 endet, muss es von q2q_2 aus einen akzeptierenden Pfad für bbbb geben. Sei dieser Pfad q2bq3bq4q_2 \xrightarrow{b} q_3 \xrightarrow{b} q_4 für Zustände q3,q4Qq_3, q_4 \in Q, sodass q4q_4 ein Endzustand ist (q4Fq_4 \in F).

4.  Da der NFA NN per Annahme reversibel ist, impliziert die Existenz eines Pfades von einem Zustand pp zu einem Zustand qq mit einem Wort ww die Existenz eines Pfades von qq nach pp mit dem gespiegelten Wort wRw^R. In unserem Fall sind die Wörter aaaa und bbbb Palindrome (aaR=aaaa^R=aa, bbR=bbbb^R=bb), daher gilt:
    *   Aus dem Pfad q0aaq2q_0 \xrightarrow{aa} q_2 folgt die Existenz eines Pfades q2aaq0q_2 \xrightarrow{aa} q_0.
    *   Aus dem Pfad q2bbq4q_2 \xrightarrow{bb} q_4 folgt die Existenz eines Pfades q4bbq2q_4 \xrightarrow{bb} q_2.

5.  Betrachten wir nun die Sprache Lq4L_{q_4}, die von NN akzeptiert wird, wenn wir in Zustand q4q_4 starten. Ein Wort ww ist in Lq4L_{q_4} genau dann, wenn es einen Pfad von q4q_4 zu einem Endzustand gibt, der mit ww beschriftet ist.

6.  Wenn ein Wort ww in Lq4L_{q_4} ist, dann ist das Wort aabbwaabbw in L(N)L(N), da es einen Pfad q0aabbq4q_0 \xrightarrow{aabb} q_4 gibt, der mit dem akzeptierenden Pfad für ww von q4q_4 aus verkettet werden kann.

7.  Gemäß der Definition von L=(aa)(bb)L = (aa)^*(bb)^* muss ein Wort, das mit aabbaabb beginnt und in LL ist, die Form aabb(bb)kaabb(bb)^k für ein k0k \ge 0 haben. Das bedeutet, wenn aabbwLaabbw \in L, muss w(bb)w \in (bb)^* sein. Folglich muss für die von q4q_4 aus akzeptierte Sprache gelten: Lq4(bb)L_{q_4} \subseteq (bb)^*.

8.  Aus den in Schritt 4 hergeleiteten Pfaden können wir einen neuen Pfad von q4q_4 aus konstruieren, indem wir sie aneinanderhängen:
    q4bbq2aaq0q_4 \xrightarrow{bb} q_2 \xrightarrow{aa} q_0.
    Dieser Pfad ist mit dem Wort bbaabbaa beschriftet.

9.  Da q0q_0 ein Endzustand ist (Schritt 1), ist dieser Pfad ein akzeptierender Pfad. Das bedeutet, das Wort bbaabbaa wird von NN akzeptiert, wenn man im Zustand q4q_4 startet. Also ist bbaaLq4bbaa \in L_{q_4}.

10. Wir haben nun einen Widerspruch:
    *   Aus Schritt 7 wissen wir: Lq4(bb)L_{q_4} \subseteq (bb)^*.
    *   Aus Schritt 9 wissen wir: bbaaLq4bbaa \in L_{q_4}.
    Jedoch ist das Wort bbaabbaa offensichtlich nicht in der Sprache (bb)(bb)^*.

Dieser Widerspruch zeigt, dass unsere anfängliche Annahme falsch sein muss. Es gibt also keinen reversiblen NFA für die Sprache L((aa)(bb))L((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, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, b -> q3
    q2, a -> q5
    q3, b -> q3
    q3, a -> q7
    q7, a -> q7
    q7, b -> q7
    q5, b -> q4
    q5, a -> q6
    q6, a -> q5
    q6, b -> q7
    q4, a -> q4
    q4, b -> q4
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
Nein. Der Automat ist nicht minimal, da er äquivalente Zustände enthält.
Zum Beispiel sind die Zustände q2q_2 und q6q_6 äquivalent.
Beide sind Endzustände.
- Bei Eingabe 'a' gehen beide in den Zustand q5q_5 über: δ(q2,a)=q5\delta(q_2, a) = q_5 und δ(q6,a)=q5\delta(q_6, a) = q_5.
- Bei Eingabe 'b' geht q2q_2 in q3q_3 über und q6q_6 in q7q_7. Die Zustände q3q_3 und q7q_7 sind ebenfalls äquivalent, da von beiden Zuständen aus jedes beliebige Wort w{a,b}w \in \{a,b\}^* zu einem Endzustand führt und somit akzeptiert wird.

Da es mindestens ein Paar äquivalenter Zustände gibt, ist der DFA nicht 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, 0), (2, 1), (2, 2)
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, 0), a -> (2, 2)
(2, 0), b -> (2, 0)
(2, 1), a -> (2, 2)
(2, 1), b -> (2, 0)
(2, 2), a -> (2, 1)
(2, 2), b -> (2, 2)

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): a
L(M1)L(M2)L(M_1)\setminus L(M_2): aab
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: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):=2nf(n):=2^n
Begründung:
Die Sprache Rc(L(M))R_c(L(M)) ist das homomorphe Bild von L(M)L(M) unter dem Homomorphismus h:{a,b,c}{a,b}h:\{a,b,c\}^* \rightarrow \{a,b\}^*, der wie folgt definiert ist: h(a)=ah(a)=a, h(b)=bh(b)=b und h(c)=εh(c)=\varepsilon. Da reguläre Sprachen unter Homomorphismen abgeschlossen sind, ist Rc(L(M))R_c(L(M)) ebenfalls regulär und es gibt einen DFA MM', der sie erkennt.

Algorithmus zur Konstruktion von M':

Sei M=(Q,{a,b,c},δ,q0,F)M=(Q, \{a,b,c\}, \delta, q_0, F) der gegebene DFA mit n=Qn=|Q| Zuständen. Wir konstruieren einen neuen DFA M=(Q,{a,b},δ,q0,F)M'=(Q', \{a,b\}, \delta', q'_0, F') wie folgt:

1.  Konstruiere einen NFA mit ε\varepsilon-Transitionen (NεN_\varepsilon):
    Wir interpretieren den DFA MM als einen NFA mit ε\varepsilon-Transitionen, NεN_\varepsilon, über dem Alphabet {a,b}\{a,b\}. Die Zustände, der Startzustand und die Endzustände bleiben gleich. Die Transitionen werden wie folgt modifiziert:
    - Für jede Transition δ(q,x)=p\delta(q, x) = p in MM mit x{a,b}x \in \{a,b\}, fügen wir eine Transition (q,x,p)(q, x, p) zu NεN_\varepsilon hinzu.
    - Für jede Transition δ(q,c)=p\delta(q, c) = p in MM, fügen wir eine ε\varepsilon-Transition (q,ε,p)(q, \varepsilon, p) zu NεN_\varepsilon hinzu.
    Dieser NεN_\varepsilon hat nn Zustände und erkennt die Sprache Rc(L(M))R_c(L(M)).

2.  Konvertiere NεN_\varepsilon zu einem DFA MM' via Potenzmengenkonstruktion:
    Wir wenden die Standard-Potenzmengenkonstruktion an, um NεN_\varepsilon in einen äquivalenten DFA MM' umzuwandeln.
    - Zustände von M': Die Zustände von MM' sind Teilmengen der Zustände von NεN_\varepsilon (und damit von MM). Also QP(Q)Q' \subseteq \mathcal{P}(Q).
    - Startzustand von M': Der Startzustand q0q'_0 ist die ε\varepsilon-Hülle des ursprünglichen Startzustands, d.h. q0=E({q0})={qQq ist von q0 in Nε durch ε-Transitionen erreichbar}q'_0 = E(\{q_0\}) = \{q \in Q \mid q \text{ ist von } q_0 \text{ in } N_\varepsilon \text{ durch } \varepsilon\text{-Transitionen erreichbar}\}.
    - Transitionen von M': Für einen Zustand SQS \in Q' und ein Zeichen x{a,b}x \in \{a,b\} wird die Nachfolgezustand δ(S,x)\delta'(S,x) wie folgt berechnet:
        1.  Bestimme die Menge aller Zustände, die von einem Zustand in SS durch eine xx-Transition erreicht werden: Sx=qS{p(q,x,p) ist eine Transition in Nε}S_x = \bigcup_{q \in S} \{ p \mid (q,x,p) \text{ ist eine Transition in } N_\varepsilon \}.
        2.  Bestimme die ε\varepsilon-Hülle dieser Menge: δ(S,x)=E(Sx)=pSxE({p})\delta'(S,x) = E(S_x) = \bigcup_{p \in S_x} E(\{p\}).
    - Endzustände von M': Ein Zustand SQS \in Q' ist ein Endzustand, wenn er mindestens einen der ursprünglichen Endzustände enthält, d.h. F={SQSF}F' = \{S \in Q' \mid S \cap F \neq \emptyset\}.
    Es werden nur die von q0q'_0 aus erreichbaren Zustände konstruiert.

Argumentation zur Zustandszahl:

Der beschriebene Algorithmus konstruiert einen DFA MM', dessen Zustände Teilmengen des Zustandsraums QQ des ursprünglichen DFA MM sind.
Da MM per Definition nn Zustände hat (Q=n|Q|=n), gibt es P(Q)=2n|\mathcal{P}(Q)| = 2^n mögliche Teilmengen von QQ.
Somit kann der resultierende DFA MM' höchstens 2n2^n Zustände haben. Unsere Wahl f(n)=2nf(n)=2^n ist also eine gültige obere Schranke für die Anzahl der Zustände von MM'.

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,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (6.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):=(ϵ0)rNull(r)r\Null(r^*) := (\epsilon \mid 0) \mid 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=r1r2r=r_1r_2:
Die Eigenschaft gilt für die direkten Teil-Ausdrücke r1r_1 und r2r_2.
(IH1): Für alle u,vΣu',v'\in\Sigma^* mit u1vL(r1)u'1v'\in L(r_1) gilt uL(Cut(r1))u'\in L(\Cut(r_1)).
(IH2): Für alle u,vΣu'',v''\in\Sigma^* mit u1vL(r2)u''1v''\in L(r_2) gilt uL(Cut(r2))u''\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1vL(r1r2)u1v \in L(r_1r_2) für beliebige u,vΣu,v\in\Sigma^*.
Per Definition von L(r1r2)L(r_1r_2) gibt es Wörter w1L(r1)w_1\in L(r_1) und w2L(r2)w_2\in L(r_2), sodass u1v=w1w2u1v = w_1w_2.
Das Zeichen '1' muss entweder in w1w_1 oder in w2w_2 vorkommen. Wir betrachten beide Fälle.

Fall 1: Das Zeichen '1' kommt in w1w_1 vor.
Dann kann man w1w_1 als w1=u1vw_1=u'1v' für gewisse u,vΣu',v'\in\Sigma^* schreiben.
Das gesamte Wort ist also u1v=(u1v)w2u1v = (u'1v')w_2.
Daraus folgt, dass u=uu=u' sein muss.
Da w1=u1vL(r1)w_1 = u'1v'\in L(r_1) gilt, können wir die Induktionshypothese (IH1) anwenden und erhalten uL(Cut(r1))u' \in L(\Cut(r_1)).
Weil u=uu=u', folgt uL(Cut(r1))u \in L(\Cut(r_1)).
Per Definition ist Cut(r1r2)=Cut(r1)r1Cut(r2)\Cut(r_1r_2) = \Cut(r_1) \mid r_1\Cut(r_2).
Da uL(Cut(r1))u \in L(\Cut(r_1)), gilt auch uL(Cut(r1)r1Cut(r2))u \in L(\Cut(r_1) \mid r_1\Cut(r_2)), und somit uL(Cut(r1r2))u\in L(\Cut(r_1r_2)).

Fall 2: Das Zeichen '1' kommt in w2w_2 vor.
Dann kann man w2w_2 als w2=u1vw_2=u''1v'' für gewisse u,vΣu'',v''\in\Sigma^* schreiben.
Das gesamte Wort ist also u1v=w1(u1v)u1v = w_1(u''1v'').
Daraus folgt, dass u=w1uu=w_1u'' sein muss.
Da w2=u1vL(r2)w_2 = u''1v''\in L(r_2) gilt, können wir die Induktionshypothese (IH2) anwenden und erhalten uL(Cut(r2))u'' \in L(\Cut(r_2)).
Wir wissen w1L(r1)w_1\in L(r_1) und uL(Cut(r2))u''\in L(\Cut(r_2)).
Also ist das Wort u=w1uu=w_1u'' in der Sprache L(r1)L(Cut(r2))=L(r1Cut(r2))L(r_1)L(\Cut(r_2)) = L(r_1\Cut(r_2)).
Per Definition ist Cut(r1r2)=Cut(r1)r1Cut(r2)\Cut(r_1r_2) = \Cut(r_1) \mid r_1\Cut(r_2).
Da uL(r1Cut(r2))u \in L(r_1\Cut(r_2)), gilt auch uL(Cut(r1)r1Cut(r2))u \in L(\Cut(r_1) \mid r_1\Cut(r_2)), und somit uL(Cut(r1r2))u\in L(\Cut(r_1r_2)).

In beiden Fällen haben wir gezeigt, dass uL(Cut(r1r2))u\in L(\Cut(r_1r_2)). Somit ist der Induktionsschritt für r=r1r2r=r_1r_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.
SABC1εS \rightarrow A \mid BC_1 \mid \varepsilon
ASC2aA \rightarrow SC_2 \mid a
BASbB \rightarrow AS \mid b
C1AAC_1 \rightarrow AA
C2AC3C_2 \rightarrow AC_3
C3BBC_3 \rightarrow BB

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.
SabAABASCS \rightarrow a \mid b \mid AA \mid BA \mid SC
AaAAA \rightarrow a \mid AA
BabAASCB \rightarrow a \mid b \mid AA \mid SC
CabAASCSSC \rightarrow a \mid b \mid AA \mid SC \mid SS

Subproblem e (3.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, C
Erreichbar: S, A, B, C
Nützlich: S, C

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 Aussage ist falsch. Wir widerlegen sie mit einem Gegenbeispiel.

Sei die endliche Sprache L={aabb}L = \{aabb\} über dem Alphabet Σ={a,b}\Sigma = \{a,b\} gegeben.

Linke Seite der Gleichung: Del(Del(L))\Del(\Del(L))

1.  Zuerst berechnen wir Del(L)=Del({aabb})\Del(L) = \Del(\{aabb\}).
    Das einzige Wort in LL ist z=aabbz=aabb. Wir suchen Zerlegungen von zz in der Form vabwvabw.
    Die einzige Möglichkeit ist v=av=a und w=bw=b, da aabb=aabba \cdot ab \cdot b = aabb.
    Das resultierende Wort ist vw=abvw=ab.
    Somit ist Del(L)={ab}\Del(L) = \{ab\}.

2.  Als Nächstes berechnen wir Del(Del(L))=Del({ab})\Del(\Del(L)) = \Del(\{ab\}).
    Das einzige Wort in der Sprache Del(L)\Del(L) ist z=abz'=ab. Wir suchen Zerlegungen von zz' in der Form vabwvabw.
    Die einzige Möglichkeit ist v=εv=\varepsilon (das leere Wort) und w=εw=\varepsilon.
    Das resultierende Wort ist vw=εvw=\varepsilon.
    Somit ist Del(Del(L))={ε}\Del(\Del(L)) = \{\varepsilon\}.

Rechte Seite der Gleichung: DelTwo(L)\DelTwo(L)

Nun berechnen wir DelTwo(L)=DelTwo({aabb})\DelTwo(L) = \DelTwo(\{aabb\}).
Laut Definition ist DelTwo(L)={uvwu,v,wΣuabvwL}\DelTwo(L) = \{uvw \mid u,v,w \in \Sigma^* \wedge uabvw \in L\}.
Wir müssen also eine Zerlegung des Wortes aabbLaabb \in L in der Form uabvwuabvw finden. Diese Form erfordert, dass das Wort mindestens zwei (nicht überlappende) Vorkommen des Teilwortes "ab" enthält.
Das Wort aabbaabb enthält das Teilwort "ab" jedoch nur genau einmal.
Daher gibt es keine solchen u,v,wΣu,v,w \in \Sigma^*, für die uabvw=aabbuabvw = aabb gilt.
Folglich ist die Menge DelTwo(L)\DelTwo(L) leer: DelTwo(L)=\DelTwo(L) = \emptyset.

Vergleich

Wir haben Del(Del(L))={ε}\Del(\Del(L)) = \{\varepsilon\} und DelTwo(L)=\DelTwo(L) = \emptyset.
Da {ε}\{\varepsilon\} \neq \emptyset, gilt die Gleichung Del(Del(L))=DelTwo(L)\Del(\Del(L)) = \DelTwo(L) nicht für die Sprache L={aabb}L=\{aabb\}.
Dies widerlegt die ursprüngliche Aussage.

Der Grund für das Scheitern der Gleichheit liegt darin, dass die Del\Del-Operation neue Vorkommen von "ab" erzeugen kann. In unserem Beispiel wird aus z=a(ab)bz=a(ab)b durch Entfernen von "ab" das Wort y=aby=ab, welches selbst ein "ab" ist. Das zweite Anwenden von Del\Del entfernt dieses neu entstandene "ab". DelTwo\DelTwo hingegen kann nur "ab"s entfernen, die bereits beide im ursprünglichen Wort vorhanden waren.

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{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':= S_{ab}$

Produktionen $P'$:
Die Menge der Produktionen $P'$ ist die Vereinigung der folgenden vier disjunkten Mengen von Produktionen. Diese werden basierend auf den Produktionen $P$ der gegebenen Grammatik $G=(V,\Sigma,P,S)$ in Chomsky-Normalform konstruiert.

**1. Erhaltung der ursprünglichen Sprache:**
Um sicherzustellen, dass $L_{G'}(X)=L_G(X)$ für alle $X\in V$ gilt, werden alle Produktionen aus $P$ in $P'$ übernommen:
*   Für jede Produktion $X \to \alpha$ in $P$, fügen wir $X \to \alpha$ zu $P'$ hinzu.
    Formell: $\{ X \to \alpha \mid (X \to \alpha) \in P \}$

**2. Produktionen für die Quotientensprache nach 'a' ($L_{G'}(X_a)$):**
Diese Produktionen leiten ein Wort $w$ ab, wenn $wa$ ein Wort in $L_G(X)$ ist.
*   Für jede Produktion der Form $X \to YZ$ in $P$, fügen wir die Produktion $X_a \to Y Z_a$ zu $P'$ hinzu.
*   Für jede Produktion der Form $X \to a$ in $P$, fügen wir die Produktion $X_a \to \varepsilon$ zu $P'$ hinzu.
    Formell: $\{ X_a \to Y Z_a \mid (X \to YZ) \in P \} \cup \{ X_a \to \varepsilon \mid (X \to a) \in P \}$

**3. Produktionen für die Quotientensprache nach 'b' ($L_{G'}(X_b)$):**
Diese Produktionen leiten ein Wort $w$ ab, wenn $bw$ ein Wort in $L_G(X)$ ist.
*   Für jede Produktion der Form $X \to YZ$ in $P$, fügen wir die Produktion $X_b \to Y_b Z$ zu $P'$ hinzu.
*   Für jede Produktion der Form $X \to b$ in $P$, fügen wir die Produktion $X_b \to \varepsilon$ zu $P'$ hinzu.
    Formell: $\{ X_b \to Y_b Z \mid (X \to YZ) \in P \} \cup \{ X_b \to \varepsilon \mid (X \to b) \in P \}$

**4. Produktionen für die $\Del$-Sprache ($L_{G'}(X_{ab})$):**
Diese Produktionen leiten die Sprache $\Del(L_G(X))$ ab. Bei einer Ableitung $X \Rightarrow YZ$ kann das zu entfernende "ab" entweder komplett im von $Y$ oder $Z$ erzeugten Teilwort liegen, oder es kann an der Grenze zwischen den beiden Teilwörtern entstehen.
*   Für jede Produktion der Form $X \to YZ$ in $P$, fügen wir die folgenden drei Produktionen zu $P'$ hinzu:
    1.  $X_{ab} \to Y_{ab} Z$ *(Deletion findet im linken Teilwort statt)*
    2.  $X_{ab} \to Y Z_{ab}$ *(Deletion findet im rechten Teilwort statt)*
    3.  $X_{ab} \to Y_a Z_b$ *(Deletion findet an der Schnittstelle statt)*

    Formell: $\{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\}$

Produktionen der Form $X \to c$ in $P$ (mit $c \in \Sigma$) erzeugen keine Wörter, die "ab" enthalten. Daher gibt es für sie keine Basisregeln für $X_{ab}$-Nichtterminale.

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:
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 S A_{ab} \mid S_a A_b
SaSAaεS_a\rightarrow S A_a \mid \varepsilon
SbSbAS_b\rightarrow S_b A
AabA\rightarrow a \mid b
AabA_{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 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 (2.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

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 (2.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|\}

Subproblem f (4.0/4.0P)

Sei LNPL\in\NP. Zeigen oder widerlegen Sie: LNPL^*\in\NP.
Ja, Beweis:Nein, Gegenbeispiel:
Sei $L \in \NP$. Dann existiert eine deterministische, polynomiell zeitbeschränkte Turingmaschine $V_L$ (der Verifizierer) und ein Polynom $p$, so dass für jedes Wort $w \in \Sigma^*$ gilt:
$w \in L \iff \exists c \in \Sigma^* \text{ mit } |c| \le p(|w|)$, so dass $V_L(w, c)$ akzeptiert.
Die Laufzeit von $V_L(w, c)$ ist durch ein Polynom $q(|w|)$ in $|w|$ beschränkt.

Wir zeigen, dass auch $L^* \in \NP$ ist, indem wir einen polynomiellen Verifizierer $V_{L^*}$ für $L^*$ konstruieren.

**Zertifikat für $w \in L^*$:**
Ein Wort $w \in\Sigma^*$ ist in $L^*$, wenn es als Konkatenation $w = w_1w_2\dots w_k$ geschrieben werden kann, wobei jedes $w_i \in L$ ist. Ein Zertifikat $C$ für $w \in L^*$ besteht aus:
1. Einer Beschreibung der Partition von $w$ in $w_1, \dots, w_k$. Dies kann durch die Angabe der $k-1$ Trennstellen als eine Folge von Indizes erfolgen.
2. Einer Konkatenation der Zertifikate $c_1, \dots, c_k$, wobei $c_i$ ein Zertifikat dafür ist, dass $w_i \in L$.
Formal kann das Zertifikat als $C = \langle \text{Indizes} \rangle \# \langle c_1 \rangle \# \dots \# \langle c_k \rangle$ kodiert werden, wobei $\#$ ein Trennzeichen ist.

**Verifizierer $V_{L^*}(w, C)$:**
1. Wenn $w = \epsilon$, akzeptiere (da $\epsilon$ per Definition in $L^*$ ist).
2. Parse das Zertifikat $C$, um die durch die Indizes definierte Partition $w=w_1 w_2 \dots w_k$ und die einzelnen Zertifikate $c_1, \dots, c_k$ zu extrahieren. Wenn $C$ kein gültiges Format hat, verwerfe.
3. Für jedes $i$ von $1$ bis $k$:
   - Rufe den Verifizierer $V_L$ mit der Eingabe $(w_i, c_i)$ auf.
   - Wenn $V_L(w_i, c_i)$ verwirft, so verwerfe auch $V_{L^*}$.
4. Wenn alle Aufrufe von $V_L$ akzeptieren, akzeptiere.

**Korrektheit:**
- *($\Rightarrow$)* Wenn $w \in L^*$, dann existiert (falls $w\neq\epsilon$) eine Zerlegung $w = w_1 \dots w_k$ mit $w_i \in L$. Für jedes dieser $w_i$ existiert ein Zertifikat $c_i$. Das aus den Indizes der Zerlegung und den Zertifikaten $c_i$ kombinierte Zertifikat $C$ wird vom Verifizierer $V_{L^*}$ akzeptiert.
- *($\Leftarrow$)* Wenn $V_{L^*}$ ein Zertifikat $C$ für $w$ akzeptiert, dann impliziert dies die Existenz einer Zerlegung $w=w_1\dots w_k$ und Zertifikate $c_i$, so dass $V_L(w_i, c_i)$ für alle $i$ akzeptiert. Das bedeutet $w_i \in L$ für alle $i$, und somit ist $w \in L^*$.

**Komplexitätsanalyse:**
Sei $n = |w|$. Wir können o.B.d.A. annehmen, dass $\epsilon \notin L$ (andernfalls betrachten wir $L' = L \setminus \{\epsilon\}$; es gilt $(L')^* = L^*$ für $L \neq \{\epsilon\}$ und $L' \in \NP$). Damit gilt für jede Zerlegung $w=w_1\dots w_k$ in nicht-leere Worte, dass die Anzahl der Teile $k \le n$ ist.

- **Länge des Zertifikats:**
  - Die $k-1$ Indizes benötigen $O(k \log n) = O(n \log n)$ Speicherplatz.
  - Die Länge der Zertifikate $c_i$ ist $|c_i| \le p(|w_i|)$. Die Gesamtlänge ist $\sum_{i=1}^k |c_i| \le \sum_{i=1}^k p(|w_i|)$. Da $p$ ein Polynom ist und $\sum_{i=1}^k |w_i| = n$, ist auch die Summe $\sum_{i=1}^k p(|w_i|)$ polynomiell in $n$. Zum Beispiel ist für $p(x)=a x^d$ die Summe $\sum a|w_i|^d \le a(\sum |w_i|)^d = an^d$.
  - Die Gesamtlänge des Zertifikats für $V_{L^*}$ ist somit polynomiell in $n$.

- **Laufzeit des Verifizierers:**
  - Das Parsen des Zertifikats ist polynomiell in dessen Länge, also auch in $n$.
  - Die Hauptarbeit sind die $k$ Aufrufe von $V_L$. Die Laufzeit von $V_L(w_i, c_i)$ ist durch $q(|w_i|)$ beschränkt.
  - Die Gesamtlaufzeit der Verifikationsschleife ist $\sum_{i=1}^k q(|w_i|)$. Analog zur Länge des Zertifikats ist diese Summe polynomiell in $n = \sum |w_i|$.
  - Die Gesamtlaufzeit von $V_{L^*}$ ist somit polynomiell in $n$.

Da ein polynomieller Verifizierer für $L^*$ existiert, gilt $L^* \in \NP$.

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
Die Aussage HAMILTON-PFAD $\le_p$ HAMILTON-KREIS gilt.

#### (1) Reduktionsfunktion

Sei $G=(V, E)$ eine beliebige Instanz von HAMILTON-PFAD. Wir konstruieren eine Instanz $G'=(V', E')$ von HAMILTON-KREIS wie folgt:

1.  Wir fügen einen neuen Knoten $w$ hinzu, der nicht in $V$ ist. Die neue Knotenmenge ist $V' = V \cup \{w\}$.
2.  Wir behalten alle Kanten aus $E$ bei und fügen für jeden Knoten $v \in V$ eine Kante zwischen $v$ und dem neuen Knoten $w$ hinzu. Die neue Kantenmenge ist $E' = E \cup \{ \{v, w\} \mid v \in V \}$.

Diese Konstruktion kann in Polynomialzeit bezüglich der Größe von $G$ durchgeführt werden.

#### (2) Anwendung auf die gegebene Instanz

Die gegebene Instanz von HAMILTON-PFAD ist der Graph $G=(V,E)$ mit:
*   Knoten $V = \{\text{A, B, C, D, E}\}$
*   Kanten $E = \{\{\text{A, B}\}, \{\text{A, C}\}, \{\text{B, C}\}, \{\text{C, D}\}, \{\text{C, E}\}, \{\text{D, E}\}\}$

Wir wenden die obige Reduktion an, um den Graphen $G'=(V',E')$ zu konstruieren:
*   **Neue Knotenmenge $V'$**: Wir fügen einen neuen Knoten hinzu, den wir $W$ nennen.
    $V' = \{\text{A, B, C, D, E, W}\}$
*   **Neue Kantenmenge $E'$**: Wir behalten alle Kanten aus $E$ und fügen Kanten von $W$ zu allen anderen Knoten hinzu.
    $E' = E \cup \{\{\text{W, A}\}, \{\text{W, B}\}, \{\text{W, C}\}, \{\text{W, D}\}, \{\text{W, E}\}\}$

Der resultierende Graph $G'$ hat somit die folgenden Kanten:
$\{\text{A, B}\}, \{\text{A, C}\}, \{\text{B, C}\}, \{\text{C, D}\}, \{\text{C, E}\}, \{\text{D, E}\}, \{\text{W, A}\}, \{\text{W, B}\}, \{\text{W, C}\}, \{\text{W, D}\}, \{\text{W, E}\}$.

*Zur Veranschaulichung: Der gegebene Graph $G$ hat einen Hamilton-Pfad, z.B. A-B-C-E-D. Gemäß unserer Reduktion sollte $G'$ einen Hamilton-Kreis haben. Der Pfad A-B-C-E-D in $G$ wird zu dem Kreis A-B-C-E-D-W-A in $G'$.*

#### Skizze der Korrektheit

Wir müssen zeigen, dass $G$ genau dann einen Hamilton-Pfad hat, wenn $G'$ einen Hamilton-Kreis hat.

**($\Rightarrow$) Annahme: $G$ hat einen Hamilton-Pfad.**
Sei $P = (v_1, v_2, \dots, v_n)$ ein Hamilton-Pfad in $G$. Dieser Pfad besucht jeden Knoten in $V$ genau einmal. Die Endknoten des Pfades sind $v_1$ und $v_n$.
In $G'$ können wir den Kreis $C = (v_1, v_2, \dots, v_n, W, v_1)$ bilden.
*   Die Kanten $\{v_i, v_{i+1}\}$ für $i \in \{1, \dots, n-1\}$ sind Kanten von $P$ und somit in $E \subseteq E'$.
*   Die Kanten $\{v_n, W\}$ und $\{W, v_1\}$ wurden bei der Konstruktion von $G'$ hinzugefügt und sind somit in $E'$.
Der Kreis $C$ besucht alle Knoten in $V' = V \cup \{W\}$ genau einmal. Also ist $C$ ein Hamilton-Kreis in $G'$.

**($\Leftarrow$) Annahme: $G'$ hat einen Hamilton-Kreis.**
Sei $C$ ein Hamilton-Kreis in $G'$. Da $W$ ein Knoten in $G'$ ist, muss $C$ den Knoten $W$ enthalten. Die Nachbarn von $W$ sind ausschließlich Knoten aus $V$. Seien $v_i, v_j \in V$ die beiden Nachbarn von $W$ in dem Kreis $C$. Der Kreis hat also die Form $(v_i, \dots, v_j, W, v_i)$.
Das Teilstück von $v_i$ nach $v_j$, nennen wir es $P'$, muss alle Knoten in $V$ genau einmal besuchen, da $C$ ein Hamilton-Kreis ist und alle Knoten aus $V'$ besucht. Da $W$ nicht zwischen $v_i$ und $v_j$ auf dem Pfad $P'$ liegt, können alle Kanten in $P'$ nur Knoten aus $V$ verbinden. Somit müssen alle Kanten von $P'$ aus der ursprünglichen Kantenmenge $E$ stammen.
Folglich ist $P'$ ein Pfad im Graphen $G$, der alle Knoten von $V$ genau einmal besucht. $P'$ ist also ein Hamilton-Pfad in $G$.

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
Die Aussage „3KNF-SAT $\le_p$ CFG-LEERHEIT“ gilt nicht unter der Annahme $\P \ne \NP$.

#### Beweis

Wir führen einen Widerspruchsbeweis.

1.  **Annahme:** Nehmen wir an, die Aussage gilt, d.h., es existiert eine polynomialzeitliche Reduktion $f$ von 3KNF-SAT auf CFG-LEERHEIT. Das bedeutet, für jede 3KNF-Formel $\phi$ können wir in Polynomialzeit eine kontextfreie Grammatik $G_\phi = f(\phi)$ konstruieren, sodass gilt:
    $\phi$ ist erfüllbar $\iff L(G_\phi) \ne \emptyset$.
    Dies ist äquivalent zu:
    $\phi$ ist **nicht** erfüllbar $\iff L(G_\phi) = \emptyset$.

2.  **Analyse von CFG-LEERHEIT:** Das Problem CFG-LEERHEIT, also zu entscheiden, ob für eine gegebene CFG $G$ die Sprache $L(G)$ leer ist, liegt in der Komplexitätsklasse $\P$.
    *   *Skizze des Algorithmus:* Man kann die Menge aller Nichtterminalsymbole bestimmen, die eine Kette von Terminalsymbolen erzeugen können.
        1.  Initialisiere eine Menge $M$ mit allen Nichtterminalen $A$, für die eine Regel $A \to w$ existiert, wobei $w$ nur aus Terminalen besteht.
        2.  Füge iterativ zu $M$ jedes Nichtterminal $B$ hinzu, für das eine Regel $B \to \alpha$ existiert, wobei alle Symbole in $\alpha$ (sowohl Terminale als auch Nichtterminale) bereits in $M$ bzw. der Menge der Terminale sind.
        3.  Wiederhole Schritt 2, bis sich $M$ nicht mehr ändert.
        4.  $L(G)$ ist genau dann nicht leer, wenn das Startsymbol $S$ in der finalen Menge $M$ enthalten ist.
    *_Dieser Algorithmus terminiert in polynomialer Zeit bezüglich der Größe der Grammatik._

3.  **Widerspruchsargumentation:**
    *   Wenn 3KNF-SAT $\le_p$ CFG-LEERHEIT gilt und CFG-LEERHEIT $\in \P$, dann würde aus der Definition der polynomialen Reduktion folgen, dass auch 3KNF-SAT $\in \P$ sein muss.
    *   *Begründung:* Ein Algorithmus für 3KNF-SAT könnte eine gegebene Formel $\phi$ mittels der Reduktion $f$ in eine Grammatik $G_\phi$ umwandeln und dann den P-Zeit-Algorithmus für CFG-LEERHEIT (bzw. dessen Komplement) auf $G_\phi$ anwenden, um die Erfüllbarkeit von $\phi$ zu entscheiden. Die Gesamtlaufzeit wäre polynomial.
    *   Das Problem 3KNF-SAT ist jedoch NP-vollständig. Wenn ein NP-vollständiges Problem in $\P$ liegt, dann folgt daraus, dass $\P = \NP$.
    *   Dies steht im direkten Widerspruch zur expliziten Annahme der Aufgabe, dass $\P \ne \NP$ gilt.

4.  **Schlussfolgerung:** Unsere ursprüngliche Annahme, dass 3KNF-SAT $\le_p$ CFG-LEERHEIT gilt, muss falsch sein. Daher gilt die Aussage nicht.

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
Die Aussage EXAKTE-ÜBERDECKUNG $\le_p$ SAT gilt. Da EXAKTE-ÜBERDECKUNG NP-vollständig ist und SAT ebenfalls NP-vollständig ist, existiert eine solche Reduktion. Wir geben eine konkrete Reduktionsfunktion an.

#### (1) Reduktionsfunktion

Sei eine Instanz von EXAKTE-ÜBERDECKUNG gegeben durch eine Menge $M=\{m_1, ..., m_k\}$ und eine Menge von Teilmengen $T=\{T_1, ..., T_n\}$. Wir konstruieren eine aussagenlogische Formel $\phi$ in konjunktiver Normalform (KNF), die genau dann erfüllbar ist, wenn eine exakte Überdeckung existiert.

1.  **Variablen:** Für jede Teilmenge $T_i \in T$ (für $i=1, ..., n$) führen wir eine boolesche Variable $x_i$ ein. Die Intuition ist, dass $x_i$ genau dann wahr ist, wenn die Teilmenge $T_i$ für die exakte Überdeckung ausgewählt wird.

2.  **Klauseln:** Wir konstruieren $\phi$ als Konjunktion zweier Arten von Klauseln:

    a.  **Jedes Element von $M$ wird überdeckt:** Für jedes Element $m_j \in M$ muss es mindestens eine ausgewählte Teilmenge $T_i$ geben, die $m_j$ enthält. Dies wird durch die folgende Klausel für jedes $j \in \{1,...,k\}$ sichergestellt:
        \[ C_j^{\text{cover}} = \bigvee_{i \text{ s.d. } m_j \in T_i} x_i \]
        Falls für ein $m_j$ keine Teilmenge $T_i$ existiert, die es enthält, ist die Disjunktion leer und somit falsch, was die resultierende Formel unerfüllbar macht (korrekt, da keine Überdeckung möglich ist).

    b.  **Jedes Element von $M$ wird höchstens einmal überdeckt:** Für jedes Element $m_j \in M$ und für jedes Paar von verschiedenen Teilmengen $T_i, T_l \in T$ (mit $i \neq l$), die beide $m_j$ enthalten, können nicht beide für die Überdeckung ausgewählt werden. Dies wird durch die folgende Klausel für jedes $j \in \{1,...,k\}$ und jedes Paar $i,l$ mit $i < l$, sodass $m_j \in T_i$ und $m_j \in T_l$, sichergestellt:
        \[ C_{j,i,l}^{\text{unique}} = (\neg x_i \vee \neg x_l) \]

Die finale Formel $\phi$ ist die Konjunktion all dieser Klauseln:
\[ \phi = \left( \bigwedge_{j=1}^{k} C_j^{\text{cover}} \right) \wedge \left( \bigwedge_{j=1}^{k} \bigwedge_{\substack{i<l \\ m_j \in T_i \\ m_j \in T_l}} C_{j,i,l}^{\text{unique}} \right) \]
Die Konstruktion dieser Formel kann in Polynomialzeit bezüglich der Größe der EXAKTE-ÜBERDECKUNG-Instanz $(|M|, |T|)$ erfolgen.

#### (2) Anwendung auf die gegebene Instanz

Gegebene Instanz:
$M=\{1,2,3,4\}$
$T=\{T_1=\{1\}, T_2=\{1,3\}, T_3=\{1,2,3\}, T_4=\{2,4\}, T_5=\emptyset\}$

Wir führen Variablen $x_1, x_2, x_3, x_4, x_5$ ein.

**a. Klauseln für die Überdeckung:**
*   Für $m=1$ (in $T_1, T_2, T_3$): $(x_1 \vee x_2 \vee x_3)$
*   Für $m=2$ (in $T_3, T_4$): $(x_3 \vee x_4)$
*   Für $m=3$ (in $T_2, T_3$): $(x_2 \vee x_3)$
*   Für $m=4$ (in $T_4$): $(x_4)$
(Anmerkung: $T_5$ enthält kein Element und taucht daher in diesen Klauseln nicht auf).

**b. Klauseln für die Eindeutigkeit:**
*   Für $m=1$ (in $T_1, T_2, T_3$): Wir benötigen Klauseln für die Paare $(T_1,T_2), (T_1,T_3), (T_2,T_3)$.
    $(\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3)$
*   Für $m=2$ (in $T_3, T_4$): Wir benötigen eine Klausel für das Paar $(T_3, T_4)$.
    $(\neg x_3 \vee \neg x_4)$
*   Für $m=3$ (in $T_2, T_3$): Wir benötigen eine Klausel für das Paar $(T_2, T_3)$.
    $(\neg x_2 \vee \neg x_3)$ (Diese Klausel wurde bereits für $m=1$ erzeugt).
*   Für $m=4$ (nur in $T_4$): Keine Paare, also keine Klauseln.

**Die resultierende SAT-Formel $\phi$ ist:**
$ (x_1 \vee x_2 \vee x_3) \wedge (x_3 \vee x_4) \wedge (x_2 \vee x_3) \wedge (x_4) \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 (\neg x_3 \vee \neg x_4) $

*Zur Veranschaulichung:* Die gegebene Instanz hat eine exakte Überdeckung $S=\{T_2, T_4\}$. Die entsprechende Belegung ist $x_2=\text{wahr}, x_4=\text{wahr}$ und $x_1=x_3=x_5=\text{falsch}$. Man kann leicht überprüfen, dass diese Belegung die Formel $\phi$ erfüllt.*

#### Skizze der Korrektheit

Wir zeigen, dass die gegebene EXAKTE-ÜBERDECKUNG-Instanz $(M, T)$ eine Lösung hat genau dann, wenn die konstruierte Formel $\phi$ erfüllbar ist.

**($\Rightarrow$) Annahme: Es existiert eine exakte Überdeckung $S \subseteq T$.**
Wir definieren eine Variablenbelegung $A$ wie folgt: $A(x_i) = \text{wahr}$, falls $T_i \in S$, und $A(x_i) = \text{falsch}$, falls $T_i \notin S$.
*   Die Klauseln der Art $C_j^{\text{cover}}$ sind erfüllt: Da $S$ eine Überdeckung ist, ist jedes $m_j \in M$ in mindestens einem (sogar genau einem) $T_i \in S$ enthalten. Für dieses $T_i$ gilt $A(x_i)=\text{wahr}$, was die Disjunktion $C_j^{\text{cover}}$ wahr macht.
*   Die Klauseln der Art $C_{j,i,l}^{\text{unique}}$ sind erfüllt: Diese Klausel hat die Form $(\neg x_i \vee \neg x_l)$. Wäre sie falsch, müssten $A(x_i)$ und $A(x_l)$ beide wahr sein. Das würde bedeuten, $T_i \in S$ und $T_l \in S$. Da aber $m_j$ in beiden Mengen ist, $T_i \cap T_l \ne \emptyset$, widerspricht dies der Eigenschaft von $S$, eine exakte Überdeckung zu sein (d.h. die Mengen in $S$ müssen paarweise disjunkt sein). Also kann dieser Fall nicht eintreten.
Somit erfüllt $A$ die Formel $\phi$.

**($\Leftarrow$) Annahme: Die Formel $\phi$ ist erfüllbar.**
Sei $A$ eine erfüllende Belegung. Wir definieren eine Lösungsmenge $S = \{ T_i \mid A(x_i)=\text{wahr} \}$. Wir müssen zeigen, dass $S$ eine exakte Überdeckung von $M$ ist.
*   Sei $m_j \in M$ ein beliebiges Element. Da die Klausel $C_j^{\text{cover}} = \bigvee_{i \text{ s.d. } m_j \in T_i} x_i$ erfüllt sein muss, muss mindestens ein $A(x_i)$ wahr sein für ein $i$, wo $m_j \in T_i$. Das bedeutet, $m_j$ ist in mindestens einer Menge aus $S$ enthalten.
*   Angenommen, $m_j$ ist in zwei verschiedenen Mengen $T_i, T_l \in S$ enthalten ($i \neq l$). Dann wären $A(x_i)$ und $A(x_l)$ beide wahr. Dies würde aber die Klausel $C_{j,i,l}^{\text{unique}} = (\neg x_i \vee \neg x_l)$ falsch machen, was der Annahme widerspricht, dass $A$ eine erfüllende Belegung ist.
Somit ist jedes Element von $M$ in genau einer Menge aus $S$ enthalten. $S$ ist also eine exakte Überdeckung.

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Σ: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\}
Beweis für Sprache 3:
Wir beweisen, dass die Sprache L3={aibjck:(i1j=k)i,j,k0}L_3 = \{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\} nicht regulär ist.
Hierfür zeigen wir, dass der Schnitt von L3L_3 mit einer regulären Sprache eine bekannte nicht-reguläre Sprache ergibt. Da reguläre Sprachen unter dem Schnitt abgeschlossen sind, beweist dies, dass L3L_3 nicht regulär sein kann.

Sei RR die reguläre Sprache, die durch den regulären Ausdruck abcab^*c^* beschrieben wird. Also R={a1bjckj,k0}R = \{a^1b^jc^k \mid j, k \ge 0\}.
Wir betrachten die Sprache L=L3RL' = L_3 \cap R. Wenn L3L_3 regulär wäre, müsste auch LL' regulär sein.

Ein Wort w=aibjckw=a^ib^jc^k liegt in LL', wenn es sowohl in L3L_3 als auch in RR liegt.
Die Zugehörigkeit zu RR erfordert i=1i=1.
Setzen wir i=1i=1 in die Bedingung für L3L_3, (i1j=k)(i\ne 1\vee j=k), ein, erhalten wir (11j=k)(1\ne 1\vee j=k), was zu (falschj=k)(\text{falsch} \vee j=k) und somit zu j=kj=k vereinfacht wird.
Ein Wort liegt also in LL', wenn es die Form a1bjcka^1b^jc^k mit j=kj=k hat.
Somit ist L={abjcjj0}L' = \{ab^jc^j \mid j \ge 0\}.

Wir beweisen nun mit dem Pumping-Lemma, dass LL' nicht regulär ist.
Angenommen, LL' ist regulär. Dann gibt es eine Pumping-Länge p1p \ge 1.
Wir wählen das Wort s=abpcps = ab^pc^p. Offensichtlich gilt sLs \in L' und s=1+2pp|s| = 1+2p \ge p.
Gemäß dem Pumping-Lemma existiert eine Zerlegung s=xyzs=xyz mit den Eigenschaften:
1. xyp|xy| \le p
2. y1|y| \ge 1
3. xykzLxy^k z \in L' für alle k0k \ge 0.

Wegen xyp|xy| \le p und der Gestalt von s=abpcps = ab^p c^p, muss die Teilzeichenkette yy innerhalb des Präfixes abp1ab^{p-1} liegen (für p2p \ge 2; für p=1p=1 ist s=abcs=abc und xy1|xy| \le 1, also y=ay=a).
Wir analysieren die möglichen Inhalte von yy:

*   Fall 1: yy enthält das Zeichen 'a'.
    Wenn yy das 'a' enthält (z.B. y=ay=a oder y=abmy=ab^m), dann enthält das Wort xy0z=xzxy^0z = xz kein 'a' mehr, oder das Wort xy2zxy^2z enthält eine ungültige Zeichenreihenfolge wie 'ba' oder mehrere 'a's. In jedem Fall ist das Ergebnis nicht von der Form abjcjab^jc^j und liegt somit nicht in LL'. Dies widerspricht Eigenschaft 3 des Pumping-Lemmas.

*   Fall 2: yy besteht nur aus 'b's.
    Dies ist die einzig verbleibende Möglichkeit. Dann hat die Zerlegung die Form x=abux=ab^u, y=bvy=b^v, z=bpuvcpz=b^{p-u-v}c^p mit u0,v1u \ge 0, v \ge 1 und u+vp1u+v \le p-1.
    Wir betrachten das Wort s=xy2z=abu(bv)2bpuvcp=abp+vcps' = xy^2z = ab^u(b^v)^2b^{p-u-v}c^p = ab^{p+v}c^p.
    In ss' ist die Anzahl der 'b's gleich p+vp+v, während die Anzahl der 'c's pp beträgt. Da v1v \ge 1, ist p+vpp+v \ne p. Folglich hat ss' nicht die Form abjcjab^jc^j und ist somit nicht in LL'. Dies widerspricht ebenfalls Eigenschaft 3 des Pumping-Lemmas.

Da für jede mögliche Zerlegung von ss ein Widerspruch entsteht, kann die Annahme, dass LL' regulär ist, nicht korrekt sein.
Da L=L3RL' = L_3 \cap R nicht regulär ist und RR regulär ist, folgt daraus, dass L3L_3 nicht regulär sein kann.

Subproblem b (0.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^*\}
no answer for choice (0)
...
answer does not follow the template

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:
Die Sprache ist L1={wΣ:L(Mw)2=25}L_1 = \{w\in\Sigma^*:|L(M_w)|^2=25\}, was äquivalent zu L1={wΣ:L(Mw)=5}L_1 = \{w\in\Sigma^*:|L(M_w)|=5\} ist, da die Größe einer Sprache nicht-negativ ist. Wir beweisen die Unentscheidbarkeit von L1L_1 durch eine Reduktion vom Halteproblem H={M,xTuringmaschine M ha¨lt auf Eingabe x}H = \{\langle M, x\rangle \mid \text{Turingmaschine } M \text{ hält auf Eingabe } x\}. Das Halteproblem ist bekanntlich unentscheidbar.

Wir konstruieren eine berechenbare Funktion ff, die eine Instanz M,x\langle M, x\rangle des Halteproblems auf eine Instanz w=f(M,x)w' = f(\langle M, x\rangle) von L1L_1 abbildet, sodass M,xH    wL1\langle M, x\rangle \in H \iff w' \in L_1.
Die Funktion ff erzeugt aus M,x\langle M, x\rangle die Beschreibung ww' einer neuen Turingmaschine MM'. Die Maschine MM' arbeitet auf einer Eingabe yy wie folgt:

1.  MM' ignoriert zunächst ihre eigene Eingabe yy und simuliert die Turingmaschine MM auf der Eingabe xx.
2.  Fall A: Wenn die Simulation von MM auf xx terminiert (also hält), geht MM' zum nächsten Schritt über. MM' überprüft, ob ihre ursprüngliche Eingabe yy eine der fünf vordefinierten Zeichenketten {0,00,000,0000,00000}\{0, 00, 000, 0000, 00000\} ist.
    *   Wenn yy eine dieser fünf Zeichenketten ist, akzeptiert MM'.
    *   Andernfalls verwirft MM'.
3.  Fall B: Wenn die Simulation von MM auf xx nicht terminiert (in eine Endlosschleife gerät), wird MM' ebenfalls nicht terminieren. In diesem Fall wird der zweite Schritt nie erreicht.

Nun analysieren wir die Sprache L(M)L(M'):
*   Wenn M,xH\langle M, x\rangle \in H, dann hält MM auf xx. Gemäß Fall A in der Konstruktion von MM' wird MM' genau dann akzeptieren, wenn die Eingabe yy eine der fünf spezifischen Zeichenketten ist. Somit ist die Sprache von MM' in diesem Fall L(M)={0,00,000,0000,00000}L(M') = \{0, 00, 000, 0000, 00000\}. Die Größe der Sprache ist L(M)=5|L(M')| = 5. Folglich liegt die Beschreibung ww' von MM' in L1L_1.
*   Wenn M,xH\langle M, x\rangle \notin H, dann hält MM auf xx nicht. Gemäß Fall B in der Konstruktion von MM' gerät diese in eine Endlosschleife und akzeptiert keine einzige Eingabe. Die Sprache von MM' ist in diesem Fall leer: L(M)=L(M') = \emptyset. Die Größe der Sprache ist L(M)=0|L(M')| = 0. Da 050 \ne 5, liegt die Beschreibung ww' von MM' nicht in L1L_1.

Die Konstruktion von w=Mw'=\langle M' \rangle aus M,x\langle M, x \rangle ist ein algorithmischer Vorgang und somit ist die Funktion ff berechenbar.
Wir haben gezeigt, dass M,xH    f(M,x)L1\langle M, x\rangle \in H \iff f(\langle M, x\rangle) \in L_1. Dies stellt eine Many-one-Reduktion von HH auf L1L_1 dar (HmL1H \le_m L_1).
Da HH unentscheidbar ist, muss auch L1L_1 unentscheidbar sein.