Exam 2024_retake.txt — x-ai/grok-4

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 2.0/3.0 12.0/13.0
5: Verlorene Buchsten 1.0/1.0 2.0/2.0 7.0/7.0 2.0/2.0 12.0/12.0
6: Quiz: Berechenbarkeit und Komplexität 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 4.0/4.0 14.0/14.0
7: Reduktion 4.0/4.0 3.0/3.0 7.0/7.0 14.0/14.0
8: Bonus 2.0/2.0 1.0/1.0 2.0/2.0 5.0/5.0
Exam total 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 L☒LLL=Σ∗LLL = \Sigma^*

Subproblem c (2.0/2.0P) 

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

Subproblem d (2.0/2.0P) 

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
☒S→SS∣aS \rightarrow SS \mid a☐S→Sa∣Sb∣εS \rightarrow Sa \mid Sb \mid \varepsilon☒S→TTT→aT∣bT∣a∣bS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P) 

Sei A⊆Σ∗A \subseteq \Sigma^* regulär und B⊆Σ∗B \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
☐A∪B‾A \cup \overline{B}☒A‾∪B\overline{A} \cup B☒ABAB

Subproblem f (3.0/3.0P) 

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

X=(a^*b^*a)^*ab
Y=((b|a)a^*|bb)^*
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,q2∈Qq_1, q_2 \in Q und für alle Zeichen x∈Σx \in \Sigma gilt: Falls q2∈δ(q1,x)q_2 \in \delta(q_1,x), so q1∈δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

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

Da ε∈L\varepsilon \in L, gilt q0∈Fq_0 \in F.

Da bb∈Lbb \in L, existiert ein Zustand v∈δ(q0,b)v \in \delta(q_0,b) und ein Pfad von vv mit bb zu einem akzeptierenden Zustand. Insbesondere existiert w∈δ(v,b)w \in \delta(v,b) mit w∈Fw \in F. Wegen Reversibilität gilt, da v∈δ(q0,b)v \in \delta(q_0,b), auch q0∈δ(v,b)q_0 \in \delta(v,b).

Da aa∈Laa \in L, existiert ein Pfad von q0q_0 mit aaaa zu einem akzeptierenden Zustand: Es gibt r∈δ(q0,a)r \in \delta(q_0,a) und s∈δ(r,a)s \in \delta(r,a) mit s∈Fs \in F.

Betrachte das Wort bbaa∉Lbbaa \notin L. Der folgende Pfad akzeptiert es: q0→bv→bq0→ar→as∈Fq_0 \xrightarrow{b} v \xrightarrow{b} q_0 \xrightarrow{a} r \xrightarrow{a} s \in F.

Dies ist ein Widerspruch, da bbaa∉Lbbaa \notin L, aber NN es akzeptiert.

Daher existiert kein solcher reversibler NFA.

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.




☐Ja☒Nein



Nein, da die Zustände q2 und q6 sowie q3 und q7 äquivalent sind. Daher hat der minimale DFA nur 6 Zustände und M ist 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): aa
L(M1)∖L(M2)L(M_1)\setminus L(M_2): aabaab
L(M2)∖L(M1)L(M_2)\setminus L(M_1): ∅\emptyset






Subproblem e (5.0/5.0P) 





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

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



Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:
Konstruiere einen \epsilon-NFA NN wie folgt:
- Zustände: dieselben wie in MM (nn Zustände).
- Startzustand: Startzustand von MM.
- Finalzustände: Finalzustände von MM.
- Transitionen:
  - Für jedes qq und σ∈{a,b}\sigma \in \{a,b\}: q→σδ(q,σ)q \xrightarrow{\sigma} \delta(q,\sigma) (wie in MM).
  - Für jedes qq: q→ϵδ(q,c)q \xrightarrow{\epsilon} \delta(q,c) (\epsilon-Transitionen simulieren cc-Übergänge).

Wende die Standardkonstruktion zur Beseitigung von \epsilon-Transitionen und Determinierung an (Potenzmengenkonstruktion mit \epsilon-Abschlüssen). Das resultierende DFA M′M' hat höchstens 2n2^n Zustände, da es höchstens 2n2^n Teilmengen der nn Zustände gibt.

M′M' erkennt Rc(L(M))R_c(L(M)), da eine akzeptierende Lauf von NN auf einem Wort w∈{a,b}∗w \in \{a,b\}^* einer Lauf von MM auf einem Wort uu entspricht, das durch Einfügen von cc's in ww entsteht (die \epsilon-Moves simulieren die cc's ohne Eingabe zu verbrauchen).








Exercise 3: Rekursive Funktionen


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





Subproblem a (1.0/1.0P) 





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



N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}






Subproblem b (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):=a∣0 a∣a 0\Null(a) := a \mid 0\,a \mid a\,0
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2∣r1Null(r2)\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2)
Null(r∗):=r∗((ϵ∣0)∣Null(r)r∗)\Null(r^*) := r^* ((\epsilon \mid 0) \mid \Null(r) r^*)






Subproblem c (6.0/6.0P) 





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

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

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

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).



Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
Die Aussage gilt für r1r_1 und r2r_2. Das heißt:

(IH1) Für alle u′,v′∈Σ∗u',v'\in\Sigma^* mit u′1v′∈L(r1)u'1v'\in L(r_1) gilt u′∈L(Cut(r1))u'\in L(\Cut(r_1)).

(IH2) Für alle u′,v′∈Σ∗u',v'\in\Sigma^* mit u′1v′∈L(r2)u'1v'\in L(r_2) gilt u′∈L(Cut(r2))u'\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^*. Dann existieren x∈L(r1)x\in L(r_1), y∈L(r2)y\in L(r_2) mit xy=u1vxy = u1v. Sei k:=∣x∣k:=|x| und m:=∣u∣+1m:=|u|+1 (Position des '1' in u1vu1v).

Fall 1: k≥mk\geq m.  
Dann liegt das '1' in xx, also x=u1x′′x = u 1 x'' für ein x′′∈Σ∗x''\in\Sigma^* (mit ∣x′′∣=k−m|x''| = k-m). Somit ist u1x′′∈L(r1)u1x''\in L(r_1).  
Nach (IH1) gilt u∈L(Cut(r1))⊆L(Cut(r1r2))u\in L(\Cut(r_1))\subseteq L(\Cut(r_1r_2)).

Fall 2: k<mk < m.  
Dann liegt das '1' in yy, also y=y′1y′′y = y' 1 y'' für y′,y′′∈Σ∗y',y''\in\Sigma^* mit ∣y′∣=m−k−1|y'|=m-k-1. Somit ist u=xy′u = x y' und v=y′′v = y''.  
Nach (IH2) gilt y′∈L(Cut(r2))y'\in L(\Cut(r_2)).  
Daher ist u=xy′∈L(r1)L(Cut(r2))⊆L(Cut(r1r2))u = x y'\in L(r_1)L(\Cut(r_2))\subseteq L(\Cut(r_1r_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 X∈VX\in V und α∈(Σ∪V)∗\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) α∈Σ∪V∗\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) ∣α∣≤2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) α≠ε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) α∉V\alpha\notin V; es gibt keine Kettenproduktionen.

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

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

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

\paragraph{Konstruktion einer Chomsky-Normalform}

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





Subproblem a (2.0/2.0P) 





Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
S→aX∣Xa∣abS \rightarrow aX \mid Xa \mid ab
X→SS∣S∣ε∣bXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Ga′G'_a an, so dass L(Ga)=L(Ga′)L(G_a) = L(G'_a) gilt und Ga′G'_a Bedingung (1) erfüllt.



S→AaX∣XAa∣AaAbS \rightarrow A_a X \mid X A_a \mid A_a A_b
X→SS∣S∣ε∣AbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_b X X
Aa→aA_a \rightarrow a
Ab→bA_b \rightarrow b






Subproblem b (2.0/2.0P) 





Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
S→A∣BAA∣εS \rightarrow A \mid BAA \mid \varepsilon
A→SABB∣aA \rightarrow SABB \mid a
B→AS∣bB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gb′G'_b an, so dass L(Gb)=L(Gb′)L(G_b) = L(G'_b) und Gb′G'_b Bedingungen (1) und (2) erfüllt.



S→A∣BC∣εS \rightarrow A \mid B C \mid \varepsilon
A→SD∣aA \rightarrow S D \mid a
B→AS∣bB \rightarrow A S \mid b
C→AAC \rightarrow A A
D→AED \rightarrow A E
E→BBE \rightarrow B B






Subproblem c (3.0/3.0P) 





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



S→AB∣DE∣B∣DS \rightarrow AB \mid DE \mid B \mid D
A→AB∣a∣BA \rightarrow AB \mid a \mid B
B→b∣BB∣DB \rightarrow b \mid BB \mid D
C→A∣cC \rightarrow A \mid c
D→BC∣BS∣BD \rightarrow BC \mid BS \mid B
E→SS∣CA∣C∣AE \rightarrow SS \mid CA \mid C \mid A






Subproblem d (3.0/3.0P) 





Entfernen von Kettenproduktionen. Die CFG GdG_d ist gegeben durch die Produktionen:
S→a∣BA∣BS \rightarrow a \mid BA \mid B
A→a∣AAA \rightarrow a \mid AA
B→b∣SC∣AB \rightarrow b \mid SC \mid A
C→B∣SSC \rightarrow B \mid SS
Führen Sie den vierten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG Gd′G'_d in CNF an, so dass L(Gd)=L(Gd′)L(G_d) = L(G'_d) gilt.



S→a∣b∣AA∣BA∣SCS \rightarrow a \mid b \mid AA \mid BA \mid SC
A→a∣AAA \rightarrow a \mid AA
B→a∣b∣AA∣SCB \rightarrow a \mid b \mid AA \mid SC
C→a∣b∣AA∣SC∣SSC \rightarrow a \mid b \mid AA \mid SC \mid SS






Subproblem e (2.0/3.0P) 





Die CFG GG ist gegeben durch die Produktionen:
S→AB∣CS \rightarrow AB\mid C
A→aA∣ASA \to aA \mid AS
B→bSB \to bS
C→aCb∣εC \to aCb \mid \varepsilon
Geben Sie die erzeugenden, erreichbaren und nützlichen Nichtterminale von GG an.





Erzeugend: S,B,CS, B, C
Erreichbar: S,A,B,CS, A, B, C
Nützlich: S,B,CS, B, C


2: mismatch










Exercise 5: Verlorene Buchsten


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





Subproblem a (1.0/1.0P) 





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



Del({abbaba,baa,ab,a,b})={ε,abba,baba}\Del(\{abbaba,baa,ab,a,b\}) = \{\varepsilon, abba, baba\}






Subproblem b (2.0/2.0P) 





Wir definieren DelTwo(L):={uvw∣u,v,w∈Σ∗∧uabvabw∈L}\DelTwo(L):=\{uvw \mid u,v,w\in \Sigma^* \wedge u ab v ab w\in L \}. Zeigen Sie oder widerlegen Sie mit einem Gegenbeispiel: Für jede endliche Sprache L⊆Σ∗L\subseteq\Sigma^* gilt
Del(Del(L))=DelTwo(L)\Del(\Del(L))=\DelTwo(L).




☐Wahr☒Falsch



Betrachten Sie die endliche Sprache L={aabb}L = \{aabb\}. 

Zuerst berechnen wir Del(L)\Del(L). Das Wort aabbaabb enthält genau ein abab, nämlich die Buchstaben an Positionen 2 und 3 (aba b). Also ist v=av = a, w=bw = b und Del(L)={ab}\Del(L) = \{ab\}.

Dann ist Del(Del(L))=Del({ab})\Del(\Del(L)) = \Del(\{ab\}). Für abab ist v=εv = \varepsilon, w=εw = \varepsilon, also Del({ab})={ε}\Del(\{ab\}) = \{\varepsilon\}. Somit gilt Del(Del(L))={ε}\Del(\Del(L)) = \{\varepsilon\}.

Nun berechnen wir DelTwo(L)\DelTwo(L). Wir suchen u,v,wu, v, w mit u ab v ab w=aabbu\, ab\, v\, ab\, w = aabb. Da ∣aabb∣=4|aabb| = 4 und ∣u ab v ab w∣=∣u∣+∣v∣+∣w∣+4|u\, ab\, v\, ab\, w| = |u| + |v| + |w| + 4, muss ∣u∣+∣v∣+∣w∣=0|u| + |v| + |w| = 0 gelten, also u=v=w=εu = v = w = \varepsilon. Aber ab ab=abab≠aabbab\, ab = abab \neq aabb. Es gibt keine anderen Möglichkeiten, da der Extralänge 0 ist. Also ist DelTwo(L)=∅\DelTwo(L) = \emptyset.

Da {ε}≠∅\{\varepsilon\} \neq \emptyset, gilt Del(Del(L))≠DelTwo(L)\Del(\Del(L)) \neq \DelTwo(L).






Subproblem c (7.0/7.0P) 





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

Hinweis: GG ist in CNF, hat also keine ε\varepsilon-Produktionen. G′G' muss nicht in CNF sein.



Startsymbol $S':=S_{ab}$
Produktionen $P'$:
- Alle Produktionen aus $P$
- Für jede Produktion $X\to YZ\in P$:
  \begin{align*}
  &X_{ab}\to Y_{ab}Z\\
  &X_{ab}\to YZ_{ab}\\
  &X_{ab}\to Y_a Z_b\\
  &X_a \to Y Z_a\\
  &X_b \to Y_b Z
  \end{align*}
- Für jede Produktion $X\to a\in P$: $X_a \to \varepsilon$
- Für jede Produktion $X\to b\in P$: $X_b \to \varepsilon$






Subproblem d (2.0/2.0P) 





Wenden Sie Ihre Konstruktion auf das Beispiel G:=({S,A},{a,b},P,S)G:=(\{S,A\},\{a,b\},P,S) an, wobei PP gegeben ist durch:
S→SA∣aA→a∣bS\to SA\mid a\qquad A\to a\mid b
Hinweis: Falls ein Nichtterminal nicht auf der linken Seite einer Produktion vorkommt, lassen Sie das entsprechende Feld leer.





Startsymbol S′:=SabS':=S_{ab}
Produktionen P′P':
S→SA∣aS\rightarrow SA \mid a
Sab→SabA∣SAab∣SaAbS_{ab}\rightarrow S_{ab}A \mid SA_{ab} \mid S_a A_b
Sa→SAa∣εS_a\rightarrow SA_a \mid \varepsilon
Sb→SbAS_b\rightarrow S_b A
A→a∣bA\rightarrow a \mid b
Aab→A_{ab}\rightarrow 
Aa→εA_a\rightarrow \varepsilon
Ab→εA_b\rightarrow \varepsilon


0 mistakes










Exercise 6: Quiz: Berechenbarkeit und Komplexität


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





Subproblem a (2.0/2.0P) 





Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?




☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar







Subproblem b (2.0/2.0P) 





Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?




☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2







Subproblem c (2.0/2.0P) 





Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?




☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0







Subproblem d (2.0/2.0P) 





Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?




☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B







Subproblem e (2.0/2.0P) 





Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?




☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}







Subproblem f (4.0/4.0P) 





Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.




☒Ja, Beweis:☐Nein, Gegenbeispiel:



Sei L∈NPL\in\NP. Dann existiert ein polynomiell zeitbeschränkter deterministischer Verifizierer VV und ein Polynom qq, sodass für jedes x∈Σ∗x\in\Sigma^* gilt: x∈Lx\in L gdw. es ein Zertifikat cc mit ∣c∣≤q(∣x∣)|c|\le q(|x|) gibt, für das V(x,c)V(x,c) akzeptiert.

Für L∗L^* konstruieren wir einen Verifizierer V∗V^* wie folgt. Sei w∈Σ∗w\in\Sigma^* mit ∣w∣=n|w|=n. Ein Zertifikat für ww codiert: eine Zahl kk (0≤k≤n0\le k\le n), Endpositionen 0=p0<p1<⋯<pk=n0=p_0 < p_1 <\dots< p_k = n (jede pip_i in Binärdarstellung mit O(log⁡n)O(\log n) Bits) und Zertifikate c1,…,ckc_1,\dots,c_k mit ∣ci∣=q(pi−pi−1)|c_i|=q(p_i - p_{i-1}) (ggf. gepaddet).

Die Gesamtlänge des Zertifikats ist O(klog⁡n)+∑q(∣wi∣)≤O(nlog⁡n)+nrO(k\log n) + \sum q(|w_i|)\le O(n\log n) + n^r für geeignetes rr (da qq polynomiell und ∑∣wi∣r≤nr\sum |w_i|^r \le n^r), also polynomiell in nn.

V∗V^* dekodiert das Zertifikat (in polynomieller Zeit), extrahiert die wi=w[pi−1+1..pi]w_i = w[p_{i-1}+1..p_i], überprüft für jedes ii mit V(wi,ci)V(w_i, c_i), ob es akzeptiert, und akzeptiert iff alle tun und die Positionen gültig sind. Für n=0n=0 akzeptiert V∗V^* direkt (leeres Wort ∈L∗\in L^*).

Die Laufzeit ist polynomiell, da Dekodierung und Kopieren/Verifizieren der k≤nk\le n Teile jeweils polynomiell Zeit benötigt, insgesamt O(poly(n))O(\mathrm{poly}(n)).

Somit ist L∗∈NPL^*\in\NP.








Exercise 7: Reduktion


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





Subproblem a (4.0/4.0P) 





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

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

Aussage: HAMILTON-PFAD ≤p\le_p HAMILTON-KREIS

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von HAMILTON-PFAD an.
Knoten: A, B, C, D, E
Kanten:
    A -- B
    A -- C
    B -- C
    C -- D
    C -- E
    D -- E




☒Die Aussage gilt☐Die Aussage gilt nicht



Reduktionsfunktion:  
Gegeben sei ein ungerichteter Graph G=(V,E)G = (V, E). Konstruiere G′=(V′,E′)G' = (V', E') wie folgt:  
- V′=V∪{k}V' = V \cup \{k\}, wobei kk ein neuer Knoten ist (nicht in VV).  
- E′=E∪{{k,v}∣v∈V}E' = E \cup \bigl\{ \{k, v\} \mid v \in V \bigr\}.  

Die Reduktionsfunktion ff bildet die Instanz GG auf G′G' ab. Diese Konstruktion ist in polynomieller Zeit möglich (Addition eines Knotens und ∣V∣|V| Kanten).  

Skizze der Korrektheit:  
GG hat einen Hamilton-Pfad ⇔\Leftrightarrow G′G' hat einen Hamilton-Kreis.  

- (⇒\Rightarrow) Sei p1−p2−⋯−pnp_1 - p_2 - \dots - p_n ein Hamilton-Pfad in GG (V={p1,…,pn}V = \{p_1, \dots, p_n\}). Dann ist pn−k−p1−p2−⋯−pnp_n - k - p_1 - p_2 - \dots - p_n ein Hamilton-Kreis in G′G' (da {pn,k}\{p_n, k\} und {k,p1}\{k, p_1\} in E′E').  
- (⇐\Leftarrow) Sei ein Hamilton-Kreis in G′G' gegeben. Da kk Grad ∣V∣|V| hat, tritt kk im Kreis zwischen zwei Knoten a,b∈Va, b \in V auf: ⋯−a−k−b−⋯−a\dots - a - k - b - \dots - a. Der Teil von bb nach aa ist ein Pfad in GG, der alle Knoten aus VV genau einmal besucht (also ein Hamilton-Pfad in GG).  

Anwendung auf die gegebene Instanz:  
Gegebener Graph G=(V,E)G = (V, E) mit  
- V={A,B,C,D,E}V = \{A, B, C, D, E\},  
- E={{A,B},{A,C},{B,C},{C,D},{C,E},{D,E}}E = \bigl\{ \{A, B\}, \{A, C\}, \{B, C\}, \{C, D\}, \{C, E\}, \{D, E\} \bigr\}.  

Der reduzierte Graph G′=(V′,E′)G' = (V', E') ist:  
- V′={A,B,C,D,E,K}V' = \{A, B, C, D, E, K\} (wähle KK als neuen Knoten),  
- E′=E∪{{K,A},{K,B},{K,C},{K,D},{K,E}}E' = E \cup \bigl\{ \{K, A\}, \{K, B\}, \{K, C\}, \{K, D\}, \{K, E\} \bigr\}.






Subproblem b (3.0/3.0P) 





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

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

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von 3KNF-SAT an.
(x1∨¬x2∨x3)∧(¬x1∨x2∨x3)(x_1\vee\neg x_2\vee x_3)\wedge(\neg x_1\vee x_2\vee x_3)




☐Die Aussage gilt☒Die Aussage gilt nicht



Die Aussage gilt nicht unter der Annahme P≠NP\P \ne \NP.  

Beweis: Angenommen, es gäbe eine polynomielle Reduktion von 3KNF-SAT nach CFG-LEERHEIT. Das bedeutet, es existiert eine in polynomieller Zeit berechenbare Funktion ff, die eine 3CNF-Formel ϕ\phi auf eine kontextfreie Grammatik G=f(ϕ)G = f(\phi) abbildet, sodass ϕ\phi erfüllbar ist genau dann, wenn L(G)=∅L(G) = \emptyset.  

Es ist bekannt, dass CFG-LEERHEIT ∈P\in \P (man kann in polynomieller Zeit alle produktiven Nichtterminale bestimmen und prüfen, ob das Startsymbol produktiv ist).  

Falls eine solche Reduktion existiert, könnte man 3KNF-SAT wie folgt in polynomieller Zeit entscheiden: Berechne G=f(ϕ)G = f(\phi) (poly-Zeit) und entscheide dann, ob L(G)=∅L(G) = \emptyset (poly-Zeit). Dies würde bedeuten, dass 3KNF-SAT ∈P\in \P. Da 3KNF-SAT NP\NP-vollständig ist, folgte P=NP\P = \NP, was der Annahme widerspricht.  

Somit kann keine solche polynomielle Reduktion existieren.






Subproblem c (7.0/7.0P) 





EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

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

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

Aussage: EXAKTE-ÜBERDECKUNG ≤p\leq_p SAT

Falls die Aussage gilt: Wenden Sie Ihre Reduktion auf folgende Instanz von EXAKTE-ÜBERDECKUNG an.
M≔{1,2,3,4}M\coloneqq\{1,2,3,4\}
T≔{T1,T2,T3,T4,T5}T\coloneqq\{T_1,T_2,T_3,T_4,T_5\}
wobei
T1≔{1}T_1\coloneqq\{1\},
T2≔{1,3}T_2\coloneqq\{1,3\},
T3≔{1,2,3}T_3\coloneqq\{1,2,3\},
T4≔{2,4}T_4\coloneqq\{2,4\},
T5≔∅T_5\coloneqq\emptyset.




☒Die Aussage gilt☐Die Aussage gilt nicht



Reduktionsfunktion:  
Gegeben eine Instanz (M,T)(M, T) von EXAKTE-ÜBERDECKUNG mit M={m1,…,mk}M = \{m_1, \dots, m_k\} und T={T1,…,Tn}T = \{T_1, \dots, T_n\}. Konstruiere eine CNF-Formel ϕ\phi wie folgt:  

- Variablen: x1,…,xnx_1, \dots, x_n, wobei xix_i wahr bedeutet, dass TiT_i in der exakten Überdeckung gewählt wird.  

Für jedes Element mj∈Mm_j \in M (für j=1,…,kj = 1, \dots, k):  
Lasse Ij={i∣mj∈Ti}I_j = \{ i \mid m_j \in T_i \} die Indizes der Teilmengen sein, die mjm_j enthalten.  

- At least one: Füge die Klausel ⋁i∈Ijxi\bigvee_{i \in I_j} x_i hinzu (falls Ij=∅I_j = \emptyset, ist dies die leere Disjunktion, was falsch ist; aber in gültigen Instanzen sollte jedes Element in mindestens einer Teilmenge vorkommen, andernfalls ist es trivial nicht überdeckbar).  
- At most one: Für jedes Paar i<li < l mit i,l∈Iji, l \in I_j füge die Klausel (¬xi∨¬xl)(\neg x_i \lor \neg x_l) hinzu.  

Die Formel ϕ\phi ist die Konjunktion aller dieser Klauseln. Die Konstruktion ist in polynomieller Zeit möglich ( polynomiell viele Klauseln, da O(n2)O(n^2) pro Element, insgesamt O(kn2)O(k n^2)).  

Skizze der Korrektheit:  
ϕ\phi ist erfüllbar ⇔\Leftrightarrow es existiert eine exakte Überdeckung S⊆TS \subseteq T.  

- (⇒\Rightarrow) Sei β\beta eine erfüllende Belegung von ϕ\phi. Definiere S={Ti∣β(xi)=1}S = \{ T_i \mid \beta(x_i) = 1 \}. Für jedes mjm_j stellt "at least one" sicher, dass mindestens eine TiT_i mit mj∈Tim_j \in T_i gewählt ist, und "at most one" stellt sicher, dass höchstens eine solche gewählt ist. Also ist SS eine exakte Überdeckung.  
- (⇐\Leftarrow) Sei SS eine exakte Überdeckung. Setze β(xi)=1\beta(x_i) = 1 gdw. Ti∈ST_i \in S. Da jedes mjm_j in genau einer Ti∈ST_i \in S vorkommt, ist für jedes jj genau eine xix_i mit i∈Iji \in I_j wahr, was beide Bedingungen ("at least one" und "at most one") erfüllt. (Falls leere Mengen in TT sind, können sie optional gewählt werden, ohne die Bedingungen zu verletzen, und entsprechen mehreren möglichen SS, aber die Existenz bleibt erhalten.)  

Anwendung auf die gegebene Instanz:  
M={1,2,3,4}M = \{1,2,3,4\}, T={T1={1},T2={1,3},T3={1,2,3},T4={2,4},T5=∅}T = \{T_1 = \{1\}, T_2 = \{1,3\}, T_3 = \{1,2,3\}, T_4 = \{2,4\}, T_5 = \emptyset\}.  

Variablen: x1,x2,x3,x4,x5x_1, x_2, x_3, x_4, x_5.  

Klauseln:  

- Für 1 (I1={1,2,3}I_1 = \{1,2,3\}):  
  At least one: (x1∨x2∨x3)(x_1 \lor x_2 \lor x_3)  
  At most one: (¬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)  

- Für 2 (I2={3,4}I_2 = \{3,4\}):  
  At least one: (x3∨x4)(x_3 \lor x_4)  
  At most one: (¬x3∨¬x4)(\neg x_3 \lor \neg x_4)  

- Für 3 (I3={2,3}I_3 = \{2,3\}):  
  At least one: (x2∨x3)(x_2 \lor x_3)  
  At most one: (¬x2∨¬x3)(\neg x_2 \lor \neg x_3)  

- Für 4 (I4={4}I_4 = \{4\}):  
  At least one: (x4)(x_4)  
  At most one: (keine Paare)  

(T_5 betrifft keine Elemente, also keine zusätzlichen Klauseln für x5x_5.)  

Die CNF-Formel ϕ\phi ist die Konjunktion all dieser Klauseln.








Exercise 8: Bonus


Mindestens eine Antwortmöglichkeit ist immer richtig.





Subproblem a (2.0/2.0P) 





Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.




☐{w∈Σ∗:∣w∣aba≠∣w∣a}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}☐({w∈Σ∗:w=wR})∗\big(\{w\in\Sigma^*:w=w^R\}\big)^*☒{aibjck:(i≠1∨j=k)∧i,j,k≥0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}



Beweis für Sprache 3:
Um zu zeigen, dass die Sprache nicht regulär ist, verwenden wir das Myhill-Nerode-Kriterium.

Betrachten wir die Präfixe wj=abjw_j = ab^j für j≥1j \geq 1.

Wir zeigen, dass für j≠kj \neq k mit j<kj < k die Präfixe wjw_j und wkw_k in verschiedenen Äquivalenzklassen liegen.

Sei z=cjz = c^j.

Dann ist wjz=abjcj∈Lw_j z = ab^j c^j \in L, da hier i=1i=1, j=jj=j und somit j=kj=k gilt, also die Bedingung (i≠1∨j=k)(i \neq 1 \lor j=k) erfüllt ist.

Dagegen ist wkz=abkcj∉Lw_k z = ab^k c^j \notin L, da i=1i=1, k>jk > j also k≠jk \neq j, und somit (i≠1∨k=j)(i \neq 1 \lor k=j) falsch ist.

Folglich sind wjw_j und wkw_k durch zz unterscheidbar und liegen in verschiedenen Klassen.

Da es unendlich viele solche jj gibt, hat LL unendlich viele Myhill-Nerode-Klassen und ist daher nicht regulär.






Subproblem b (1.0/1.0P) 





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

Hinweis: Um das Feld leerzulassen, geben Sie - an.




☒L(b∗a∗b)L(b^*a^*b)☐{w∈Σ∗:w≠wR}\{w\in\Sigma^*:w\ne w^R\}☒{uavv:u,v∈Σ∗}\{uavv:u,v\in\Sigma^*\}



1: abab
2: −-
3: aabaab






Subproblem c (2.0/2.0P) 





Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.




☒{w∈Σ∗:∣L(Mw)∣2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}☐{w∈Σ∗:∣L(Mw)∣2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}☒{w∈Σ∗:∣L(Mw)∣2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}



Beweis für Sprache 1:
Angenommen, die Menge {w∈Σ∗:∣L(Mw)∣2=25}\{w \in \Sigma^* : |L(M_w)|^{2} = 25\} wäre entscheidbar. Das bedeutet, es gibt eine Turingmaschine DD, die für eine gegebene Kodierung ⟨M⟩=w\langle M \rangle = w entscheidet, ob ∣L(M)∣=5|L(M)| = 5 (da 52=255^2 = 25 und unendliche Kardinalitäten nicht zu 25 quadriert werden).

Wir reduzieren das Leerheitsproblem, das unentscheidbar ist, darauf.

Gegeben eine TM MM (Kodierung ⟨M⟩\langle M \rangle), konstruieren wir M′M' wie folgt:

Auf Eingabe yy:
- Wenn y=1ky = 1^k für k=1,2,3,4,5k=1,2,3,4,5, akzeptiere.
- Sonst, wenn yy mit 00 beginnt, sei zz das Wort ohne das erste 00; simuliere MM auf zz und akzeptiere genau dann, wenn MM zz akzeptiert.
- Andernfalls lehne ab.

Dann ist L(M′)={1,11,111,1111,11111}∪{0z∣z∈L(M)}L(M') = \{1, 11, 111, 1111, 11111\} \cup \{0z \mid z \in L(M)\}.

Diese Vereinigung ist disjunkt, da die ersten Wörter mit 11 beginnen und die zweiten mit 00.

Folglich ∣L(M′)∣=5+∣L(M)∣|L(M')| = 5 + |L(M)|, falls ∣L(M)∣|L(M)| endlich ist, und unendlich sonst.

Insbesondere gilt ∣L(M′)∣=5|L(M')| = 5 genau dann, wenn ∣L(M)∣=0|L(M)| = 0, d.h. L(M)=∅L(M) = \emptyset.

Könnte DD auf ⟨M′⟩\langle M' \rangle angewendet werden, so könnte man das Leerheitsproblem für MM entscheiden, was unmöglich ist.

Daher ist die Sprache unentscheidbar.