Exam 2024_retake.txt — deepseek/deepseek-r1-0528

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 0.0/3.0 13.0/16.0
2: DFA-Algorithmen 0.0/6.0 0.0/1.0 4.0/4.0 2.0/2.0 5.0/5.0 11.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 2.0/3.0 12.0/13.0
5: Verlorene Buchsten 1.0/1.0 2.0/2.0 6.0/7.0 0.0/2.0 9.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 0.0/2.0 4.0/4.0 12.0/14.0
7: Reduktion 4.0/4.0 3.0/3.0 7.0/7.0 14.0/14.0
8: Bonus 1.0/2.0 1.0/1.0 2.0/2.0 4.0/5.0
Exam total 88.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)Y=(a \mid b)^*
Z=Z=\emptyset

Subproblem g (0.0/3.0P)

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

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Beweis durch Widerspruch: Angenommen, es gibt einen reversiblen NFA N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F) mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*).

Betrachte das Wort aaLaa \in L. Es gibt einen akzeptierenden Lauf, etwa q0arapq_0 \xrightarrow{a} r \xrightarrow{a} p mit pFp \in F.  
- Wegen Reversibilität gilt: Aus pδ(r,a)p \in \delta(r, a) folgt rδ(p,a)r \in \delta(p, a).  
- Für das Wort abLab \notin L gibt es einen Lauf, der im gleichen Zustand rr nach dem ersten aa endet (nicht notwendig derselbe Lauf, aber ein Zustand rr mit q0arq_0 \xrightarrow{a} r für aaaa). Somit existiert ein Zustand ss mit δ(r,b)=s\delta(r, b) = s.  
- Reversibilität impliziert: Aus sδ(r,b)s \in \delta(r, b) folgt rδ(s,b)r \in \delta(s, b).

Nun konstruieren wir einen Lauf für abbaLabba \notin L:  
- q0arq_0 \xrightarrow{a} r (nach erstem aa)  
- rbsr \xrightarrow{b} s (nach abab)  
- sbrs \xrightarrow{b} r (da δ(s,b)=r\delta(s, b) = r)  
- rapr \xrightarrow{a} p (da δ(r,a)p\delta(r, a) \ni p)  
Endzustand pFp \in F ist akzeptierend.

Dies wäre eine akzeptierende Berechnung für abbaabba, aber abbaLabba \notin L (da bb vor dem letzten aa), Widerspruch.  
Also existiert kein solcher reversibler NFA.

Exercise 2: DFA-Algorithmen


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

Subproblem b (0.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
The DFA MM is not minimal because it contains equivalent states. Specifically:  
- States q2q_2 and q5q_5 are equivalent (both represent sets containing final state 22 from NN, and their transitions yield identical behavior).  
- States q4q_4, q6q_6, and q7q_7 are equivalent (all represent the empty set \emptyset, acting as non-final sinks).  
Merging these states would reduce MM to a smaller equivalent DFA.

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: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:
Um den DFA MM' für Rc(L(M))R_c(L(M)) zu konstruieren, wird folgender Algorithmus verwendet:
1. Berechne für jeden Zustand qq in MM die ε\varepsilon-Hülle bzgl. cc: \textscECLOSE(q)\textsc{ECLOSE}(q) = alle durch cc-Übergänge von qq erreichbaren Zustände.
2. Erstelle einen NFA NN mit denselben Zuständen wie MM, Startzustand q0q_0 und Finalzustandsmenge FF. Die Übergänge für a,ba,b sind:
  δN(q,σ)=r\textscECLOSE(q)\textscECLOSE(δ(r,σ))\delta_N(q, \sigma) = \bigcup_{r \in \textsc{ECLOSE}(q)} \textsc{ECLOSE}\big( \delta(r,\sigma) \big) für σ{a,b}\sigma \in \{a,b\}.
3. Wende Potenzmengenkonstruktion auf NN an, um MM' zu erhalten: Zustände sind Teilmengen von QQ (der Zustände von MM).

Da MM nn Zustände hat, gibt es höchstens 2n2^n Teilmengen. Somit hat MM' maximal 2n2^n Zustände.

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):=0aa0a\Null(a) := 0a \mid a0 \mid a
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r10r2r1Null(r2)\Null(r_1 r_2) := \Null(r_1) \cdot r_2 \mid r_1 \cdot 0 \cdot r_2 \mid r_1 \cdot \Null(r_2)
Null(r):=rrNull(r)rr0r\Null(r^*) := r^* \mid r^* \cdot \Null(r) \cdot r^* \mid r^* \cdot 0 \cdot 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:
- Für r1r_1: Für alle u,vΣu, v \in \Sigma^* mit u1vL(r1)u1v \in L(r_1) gilt uL(Cut(r1))u \in L(\text{Cut}(r_1)).
- Für r2r_2: Für alle u,vΣu, v \in \Sigma^* mit u1vL(r2)u1v \in L(r_2) gilt uL(Cut(r2))u \in L(\text{Cut}(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1vL(r1r2)u1v \in L(r_1 r_2). Dann existieren w1L(r1)w_1 \in L(r_1) und w2L(r2)w_2 \in L(r_2) mit u1v=w1w2u1v = w_1 w_2.

1. Fall 1: Das '1' liegt in w1w_1.
   - Dann ist w1=u1vw_1 = u'1v' für geeignete u,vΣu', v' \in \Sigma^* mit u=uu = u' und vw2=vv' w_2 = v.
   - Da w1=u1vL(r1)w_1 = u'1v' \in L(r_1), folgt aus der Induktionshypothese für r1r_1, dass uL(Cut(r1))u' \in L(\text{Cut}(r_1)).
   - Weil Cut(r1r2)=Cut(r1)r1Cut(r2)\text{Cut}(r_1 r_2) = \text{Cut}(r_1) \mid r_1 \text{Cut}(r_2), ist L(Cut(r1))L(Cut(r1r2))L(\text{Cut}(r_1)) \subseteq L(\text{Cut}(r_1 r_2)).
   - Also: u=uL(Cut(r1r2))u = u' \in L(\text{Cut}(r_1 r_2)).

2. Fall 2: Das '1' liegt in w2w_2.
   - Dann ist w2=u1vw_2 = u''1v'' für geeignete u,vΣu'', v'' \in \Sigma^* mit u=w1uu = w_1 u'' und v=vv'' = v.
   - Da w2=u1vL(r2)w_2 = u''1v'' \in L(r_2), folgt aus der Induktionshypothese für r2r_2, dass uL(Cut(r2))u'' \in L(\text{Cut}(r_2)).
   - Dann ist w1uL(r1Cut(r2))w_1 u'' \in L(r_1 \text{Cut}(r_2)), da w1L(r1)w_1 \in L(r_1) und uL(Cut(r2))u'' \in L(\text{Cut}(r_2)).
   - Weil Cut(r1r2)=Cut(r1)r1Cut(r2)\text{Cut}(r_1 r_2) = \text{Cut}(r_1) \mid r_1 \text{Cut}(r_2), ist L(r1Cut(r2))L(Cut(r1r2))L(r_1 \text{Cut}(r_2)) \subseteq L(\text{Cut}(r_1 r_2)).
   - Also: u=w1uL(Cut(r1r2))u = w_1 u'' \in L(\text{Cut}(r_1 r_2)).

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_a X \mid X A_a \mid A_a A_b
XSSSεAbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_b X X
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 B C_1 \mid \varepsilon
ASC2aA \rightarrow S C_2 \mid a
BASbB \rightarrow A S \mid b
C1AAC_1 \rightarrow A A
C2AC3C_2 \rightarrow A C_3
C3BBC_3 \rightarrow B B

Subproblem c (3.0/3.0P)

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

Subproblem e (2.0/3.0P)

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

Exercise 5: Verlorene Buchsten

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

Subproblem a (1.0/1.0P)

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

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 Behauptung ist falsch. Ein Gegenbeispiel ist L={aabb}L = \{aabb\}.  
- Del(L)={ab}\Del(L) = \{ab\},  
- Del(Del(L))=Del({ab})={ε}\Del(\Del(L)) = \Del(\{ab\}) = \{\varepsilon\},  
- DelTwo(L)={uvwuabvabw{aabb}}=\DelTwo(L) = \{uvw \mid u ab v ab w \in \{aabb\}\} = \emptyset,  
da aabbaabb nicht als uabvabwu ab v ab w mit u,v,wΣu, v, w \in \Sigma^* geschrieben werden kann.  
Daher gilt Del(Del(L))DelTwo(L)\Del(\Del(L)) \neq \DelTwo(L).

Subproblem c (6.0/7.0P)

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

Hinweis: GG ist in CNF, hat also keine ε\varepsilon-Produktionen. GG' muss nicht in CNF sein.
Startsymbol S=SabS' = S_{ab}  
Produktionen PP':  
- Alle Produktionen aus PP.  
- Für jede Produktion XYZX \to YZ in PP:  
  XabYabZYZabYaZb\quad X_{ab} \to Y_{ab} Z \mid Y Z_{ab} \mid Y_a Z_b  
  XaYZa\quad X_a \to Y Z_a  
  XbYbZ\quad X_b \to Y_b Z  
- Für jede Produktion XaX \to a in PP:  
  \quad Wenn a=aa = a: XaϵX_a \to \epsilon; sonst: keine Produktion für XaX_a  
  \quad Wenn a=ba = b: XbϵX_b \to \epsilon; sonst: keine Produktion für XbX_b  
  \quad Keine Produktion für XabX_{ab}  
- Für jede Produktion XbX \to b in PP:  
  \quad Wenn a=aa = a: XaϵX_a \to \epsilon; sonst: keine Produktion für XaX_a  
  \quad Wenn a=ba = b: XbϵX_b \to \epsilon; sonst: keine Produktion für XbX_b  
  \quad Keine Produktion für XabX_{ab}

Subproblem d (0.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
answer does not follow the template

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 (0.0/2.0P)

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

Subproblem f (4.0/4.0P)

Sei LNPL\in\NP. Zeigen oder widerlegen Sie: LNPL^*\in\NP.
Ja, Beweis:Nein, Gegenbeispiel:
Beweis: Da LNP L \in \text{NP} , existiert ein polynomieller Verifizierer V V  für L L  mit einer Laufzeitbeschränkung durch ein Polynom p p . Wir konstruieren einen nichtdeterministischen polynomiellen Verifizierer V V'  für L L^*  wie folgt:  

Bei Eingabe w w  (mit w=n |w| = n ) und Zertifikat c c :  
1. Wenn w=ε w = \varepsilon , akzeptiere (denn εL \varepsilon \in L^*  per Definition).  
2. Rate nichtdeterministisch eine Zerlegung von w w  in k1 k \geq 1  Teilwörter w1,w2,,wk w_1, w_2, \dots, w_k  mit w=w1w2wk w = w_1 w_2 \cdots w_k . Dies entspricht dem Raten von k1 k-1  Trennstellen 0=i0<i1<i2<<ik=n 0 = i_0 < i_1 < i_2 < \dots < i_k = n , wobei wj=w[ij1+1bisij] w_j = w[i_{j-1}+1 \, \text{bis} \, i_j]  für j=1,,k j = 1, \dots, k .  
3. Rate für jedes Teilwort wj w_j  ein Zertifikat cj c_j  der Länge höchstens p(wj) p(|w_j|) . Das Gesamtzertifikat c c  besteht aus der Beschreibung der Trennstellen und den cj c_j .  
4. Verifiziere für jedes j j , dass V(wj,cj) V(w_j, c_j)  akzeptiert (d.h., wjL w_j \in L ).  
5. Akzeptiere nur, wenn alle V(wj,cj) V(w_j, c_j)  akzeptieren; andernfalls verwerfe.  

Korrektheit und Laufzeit:  
- Die Anzahl der Trennstellen k1 k-1  ist durch n n  beschränkt, daher hat ihre Beschreibung Länge O(nlogn) O(n \log n) .  
- Die Zertifikate cj c_j  haben jeweils Länge p(wj)p(n) \leq p(|w_j|) \leq p(n) , und ihre Gesamtlänge ist höchstens kp(n)np(n) k \cdot p(n) \leq n \cdot p(n) , also polynomiell in n n .  
- Die Verifikation mit V V  für jedes wj w_j  dauert Zeit p(wj)p(n) \leq p(|w_j|) \leq p(n) . Die Summe dieser Zeiten ist kp(n)np(n) \leq k \cdot p(n) \leq n \cdot p(n) , ebenfalls polynomiell.  
Daher akzeptiert V V'  ein Wort w w  genau dann, wenn wL w \in L^* , und läuft in nichtdeterministischer Polynomzeit. Somit ist LNP L^* \in \text{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 Reduktionsfunktion ff wird wie folgt definiert:  
Gegeben einen ungerichteten Graphen G=(V,E)G = (V, E) als Instanz von HAMILTON-PFAD, konstruieren wir einen neuen Graphen f(G)=G=(V,E)f(G) = G' = (V', E'), wobei:
- V=V{s}V' = V \cup \{s\} mit einem neuen Knoten sVs \notin V,
- E=E{{s,v}vV}E' = E \cup \{\{s, v\} \mid v \in V\}.

Diese Reduktion ist polynomiell, da nur ein zusätzlicher Knoten und n=Vn = |V| Kanten hinzugefügt werden.

Korrektheitsskizze:  
- Ja-Instanzen: Hat GG einen Hamilton-Pfad v1,v2,,vnv_1, v_2, \dots, v_n, so bildet s,v1,v2,,vn,ss, v_1, v_2, \dots, v_n, s einen Hamilton-Kreis in GG', da ss mit allen Knoten verbunden ist und somit direkt an v1v_1 und vnv_n angeschlossen ist.  
- Nein-Instanzen: Hat GG' einen Hamilton-Kreis, muss dieser den Knoten ss enthalten. Die beiden Nachbarn von ss im Kreis sind Knoten uu und ww aus VV. Der Pfad zwischen uu und ww in diesem Kreis (ohne ss) ist ein Hamilton-Pfad in GG, da alle Knoten aus VV durchlaufen werden und die Kanten in EE liegen.  

Anwendung auf die gegebene Instanz:  
- Eingabe (HAMILTON-PFAD):  
  - Knoten: V={A,B,C,D,E}V = \{A, B, C, D, E\}  
  - Kanten: E={{A,B},{A,C},{B,C},{C,D},{C,E},{D,E}}E = \{\{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}, \{C,E\}, \{D,E\}\}  
- Ausgabe (HAMILTON-KREIS):  
  - Knoten: V={A,B,C,D,E,s}V' = \{A, B, C, D, E, s\}  
  - Kanten: E=E{{s,A},{s,B},{s,C},{s,D},{s,E}}E' = E \cup \{\{s,A\}, \{s,B\}, \{s,C\}, \{s,D\}, \{s,E\}\}  
  Explizit:  
  - Ursprüngliche Kanten: {A,B},{A,C},{B,C},{C,D},{C,E},{D,E}\{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}, \{C,E\}, \{D,E\}  
  - Hinzugefügte Kanten: {s,A},{s,B},{s,C},{s,D},{s,E}\{s,A\}, \{s,B\}, \{s,C\}, \{s,D\}, \{s,E\}

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 gilt nicht.  
Beweis:  
Angenommen, 3KNF-SATpCFG-LEERHEIT3\text{KNF-SAT} \leq_p \text{CFG-LEERHEIT}.  
- CFG-LEERHEITP\text{CFG-LEERHEIT} \in \P, da in Polynomzeit entscheidbar ist, ob L(G)=L(G) = \emptyset durch Entfernen unerreichbarer/ohne Terminierbarkeit nicht-produktiver Symbole.  
- Unter PNP\P \neq \NP folgt 3KNF-SATP3\text{KNF-SAT} \in \P, da die Reduktion und CFG-LEERHEITP\text{CFG-LEERHEIT} \in \P eine Polynomzeitalgorithmus für 3KNF-SAT3\text{KNF-SAT} implizieren.  
- Aber 3KNF-SAT3\text{KNF-SAT} ist NP\NP-vollständig, sodass 3KNF-SATP3\text{KNF-SAT} \in \P NPP\NP \subseteq \P und somit P=NP\P = \NP impliziert, im Widerspruch zur Annahme PNP\P \neq \NP.  
Folglich existiert keine polynomielle Reduktion von 3KNF-SAT3\text{KNF-SAT} auf CFG-LEERHEIT\text{CFG-LEERHEIT}.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

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

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

Aussage: EXAKTE-ÜBERDECKUNG p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M{1,2,3,4}M\coloneqq\{1,2,3,4\}
T{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1{1}T_1\coloneqq\{1\},
T2{1,3}T_2\coloneqq\{1,3\},
T3{1,2,3}T_3\coloneqq\{1,2,3\},
T4{2,4}T_4\coloneqq\{2,4\},
T5T_5\coloneqq\emptyset.
Die Aussage giltDie Aussage gilt nicht
Reduktionsfunktion:  
Gegeben eine Instanz (M,T)(M, T) von EXAKTE-ÜBERDECKUNG mit M={m1,,mk}M = \{m_1, \dotsc, m_k\} und T={T1,,Tn}T = \{T_1, \dotsc, T_n\}, konstruieren wir eine boolesche Formel ϕ\phi in KNF wie folgt:
- Variablen: Für jede Teilmenge TiT_i definieren wir eine Variable xix_i, die wahr ist, wenn TiT_i in der Überdeckung SS enthalten ist.
- Klauseln: 
  1. Für jedes Element mMm \in M:
     - Klausel für Mindestüberdeckung: i:mTixi\bigvee_{i: m \in T_i} x_i (mindestens ein TiT_i mit mTim \in T_i wird ausgewählt).
     - Klauseln für Eindeutigkeit: Für jedes Paar i,ji, j mit i<ji < j und mTiTjm \in T_i \cap T_j die Klausel ¬xi¬xj\neg x_i \lor \neg x_j (höchstens ein TiT_i wird ausgewählt).
  2. Leere Teilmengen Ti=T_i = \emptyset führen zu keiner Klausel, da keine Elemente abgedeckt werden.

Die Formel ϕ\phi ist die Konjunktion aller Klauseln. Die Reduktion läuft in Polynomzeit, da die Anzahl der Klauseln durch O(kn2)O(k \cdot n^2) beschränkt ist (mit M=k|M| = k, T=n|T| = n).

Korrektheitsskizze:  
- Ja-Instanzen: Wenn es eine exakte Überdeckung STS \subseteq T gibt, setze xi=1x_i = 1 für TiST_i \in S, sonst 00. Jede Klausel ist erfüllt: Die Mindestüberdeckungs-Klausel gilt für jedes mm, da genau ein TiT_i mit mTim \in T_i in SS ist. Die Eindeutigkeits-Klauseln sind erfüllt, da kein mm in mehreren TiST_i \in S vorkommt.
- Nein-Instanzen: Wenn kein exakte Überdeckung existiert, ist ϕ\phi unerfüllbar, da entweder ein Element nicht abgedeckt wird (Mindestüberdeckung verletzt) oder sich Überlappungen ergeben (Eindeutigkeit verletzt).

Anwendung auf die gegebene Instanz:  
- Eingabe:
  - M={1,2,3,4}M = \{1, 2, 3, 4\}
  - T={T1,T2,T3,T4,T5}T = \{T_1, T_2, T_3, T_4, T_5\} mit T1={1}T_1 = \{1\}, T2={1,3}T_2 = \{1, 3\}, T3={1,2,3}T_3 = \{1, 2, 3\}, T4={2,4}T_4 = \{2, 4\}, T5=T_5 = \emptyset.
- Variablen: x1x_1 für T1T_1, x2x_2 für T2T_2, x3x_3 für T3T_3, x4x_4 für T4T_4, x5x_5 für T5T_5 (entfällt, da in keiner Klausel).
- Klauseln:
  - m=1m=1:  
    - I1={1,2,3}I_1 = \{1,2,3\} → Klausel: x1x2x3x_1 \lor x_2 \lor x_3  
    - Paare: (1,2),(1,3),(2,3)(1,2),(1,3),(2,3) → Klauseln: ¬x1¬x2\neg x_1 \lor \neg x_2, ¬x1¬x3\neg x_1 \lor \neg x_3, ¬x2¬x3\neg x_2 \lor \neg x_3  
  - m=2m=2:  
    - I2={3,4}I_2 = \{3,4\} → Klausel: x3x4x_3 \lor x_4  
    - Paar: (3,4)(3,4) → Klausel: ¬x3¬x4\neg x_3 \lor \neg x_4  
  - m=3m=3:  
    - I3={2,3}I_3 = \{2,3\} → Klausel: x2x3x_2 \lor x_3  
    - Paar: (2,3)(2,3) → Klausel: ¬x2¬x3\neg x_2 \lor \neg x_3 (bereits vorhanden)  
  - m=4m=4:  
    - I4={4}I_4 = \{4\} → Klausel: x4x_4  
    - Kein Paar.  
- KNF-Formel ϕ\phi:  
  (x1x2x3)(¬x1¬x2)(¬x1¬x3)(¬x2¬x3)(x3x4)(¬x3¬x4)(x2x3)(x4)
  (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_3) \land (\neg x_2 \lor \neg x_3) \land (x_3 \lor x_4) \land (\neg x_3 \lor \neg x_4) \land (x_2 \lor x_3) \land (x_4)
  

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (1.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
wrong answer for choice (0)
Beweis für Sprache 3:
Wir zeigen, dass die Sprache L={aibjck:(i1j=k)i,j,k0}L = \{ a^i b^j c^k : (i \ne 1 \vee j = k) \wedge i,j,k \ge 0 \} nicht regulär ist, indem wir die Abschlusseigenschaften regulärer Sprachen nutzen. Betrachten wir die Sprache L={wΣ:w hat die Form aibjck mit i=1}L' = \{ w \in \Sigma^* : w \text{ hat die Form } a^i b^j c^k \text{ mit } i=1 \}. Da LL' regulär ist (erkennbar durch einen endlichen Automaten, der prüft, dass das erste Zeichen aa ist und kein weiteres aa folgt, gefolgt von beliebig vielen bb und dann cc), müssen wir den Schnitt LLL \cap L' bilden:
LL={abjck:j=k}={abjcj:j0}.
L \cap L' = \{ a b^j c^k : j = k \} = \{ a b^j c^j : j \ge 0 \}.

Die Sprache {abjcj:j0}\{ a b^j c^j : j \ge 0 \} ist nicht regulär, da sie das Pumping-Lemma für reguläre Sprachen verletzt (analog zur Sprache {bjcj}\{ b^j c^j \}). Wenn LL regulär wäre, dann müsste auch LLL \cap L' regulär sein, weil reguläre Sprachen unter Schnitt abgeschlossen sind. Da jedoch LLL \cap L' nicht regulär ist, ist LL nicht regulär.

Subproblem b (1.0/1.0P)

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

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

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 L1={wΣ:L(Mw)2=25}={wΣ:L(Mw)=5}L_1 = \{w \in \Sigma^* : |L(M_w)|^2 = 25\} = \{w \in \Sigma^* : |L(M_w)| = 5\} ist unentscheidbar. Wir beweisen dies durch Reduktion des spezifischen Halteproblems 
H={M,w:M ha¨lt und akzeptiert w} H = \{\langle M, w \rangle : M \text{ hält und akzeptiert } w\} 
auf L1L_1. Seien v1,v2,v3,v4,v5v_1, v_2, v_3, v_4, v_5 fünf verschiedene Wörter über Σ={0,1}\Sigma = \{0,1\} (z.B. ε,0,1,00,01\varepsilon, 0, 1, 00, 01). Konstruiere für eine gegebene TM MM und ein Wort ww eine TM NM,wN_{M,w}:

NM,wN_{M,w} bei Eingabe xx:
1. Falls x{v1,v2,v3,v4,v5}x \notin \{v_1, v_2, v_3, v_4, v_5\}, verwerfe.
2. Falls x=vix = v_i für ein i{1,2,3,4,5}i \in \{1, 2, 3, 4, 5\}: simuliere MM auf Eingabe ww.  
   - Akzeptiere, falls MM ww akzeptiert; andernfalls verwerfe.

Es gilt:
- Akzeptiert MM die Eingabe ww, werden alle viv_i akzeptiert: L(NM,w)=5|L(N_{M,w})| = 5.
- Akzeptiert MM ww nicht (Ablehnung oder Endlosschleife), wird kein xx akzeptiert: L(NM,w)=0|L(N_{M,w})| = 0.

Also: M,wH\langle M, w \rangle \in H gdw. NM,wL1\langle N_{M,w} \rangle \in L_1. Da HH unentscheidbar ist, ist L1L_1 unentscheidbar.