Exam 2024_retake.txt — deepseek/deepseek-chat-v3.1

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 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 5.0/6.0 6.0/6.0 12.0/13.0
4: CFG-Algorithmen 2.0/2.0 2.0/2.0 3.0/3.0 3.0/3.0 2.0/3.0 12.0/13.0
5: Verlorene Buchsten 1.0/1.0 2.0/2.0 7.0/7.0 2.0/2.0 12.0/12.0
6: Quiz: Berechenbarkeit und Komplexität 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 4.0/4.0 14.0/14.0
7: Reduktion 4.0/4.0 3.0/3.0 7.0/7.0 14.0/14.0
8: Bonus 2.0/2.0 1.0/1.0 2.0/2.0 5.0/5.0
Exam total 100.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|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, dass kein reversibler NFA für L((aa)(bb))L((aa)^*(bb)^*) existiert:

Angenommen, es gibt einen reversiblen NFA NN mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*). Da NN reversibel ist, muss für jede Transition von Zustand pp zu Zustand qq auf Symbol xx eine Transition von qq zu pp auf xx existieren.

Betrachte die Zeichenkette bbLbb \in L. Nach Lesen von bbbb ist NN in einem Akzeptanzzustand qaccq_{acc}. Aufgrund der Reversibilität muss von qaccq_{acc} auf bb eine Transition zu einem Zustand qbq_b existieren, von dem aus auf bb eine Transition zu qaccq_{acc} führt. Da bbbb akzeptiert wird, muss von qbq_b auf bb nach qaccq_{acc} gehen.

Nun betrachte die Zeichenkette bLb \notin L. Nach Lesen von bb ist NN in einem Zustand qbq_b (nicht akzeptierend). Von qbq_b auf aa muss es eine Transition zu einem Zustand rr geben, da baLba \notin L und thus nicht akzeptiert werden darf. Aufgrund der Reversibilität muss von rr auf aa eine Transition zurück zu qbq_b existieren.

Jetzt kann NN die Zeichenkette baba lesen: von Start nach qbq_b auf bb, dann nach rr auf aa. Von rr aus kann auf aa nach qbq_b gegangen werden, und von qbq_b auf bb nach qaccq_{acc}. Thus wird die Zeichenkette baabbaab akzeptiert. However, baabbaab enthält aa nach bb und ist nicht in L((aa)(bb))L((aa)^*(bb)^*), da alle aa vor den bb stehen müssen. Dies ist ein Widerspruch zur Annahme that L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*).

Daher existiert kein reversibler NFA für 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, a -> q4
    q0, b -> q1
    q1, a -> q4
    q1, b -> q2
    q2, a -> q5
    q2, b -> q3
    q3, a -> q7
    q3, b -> q3
    q4, a -> q4
    q4, b -> q4
    q5, a -> q6
    q5, b -> q4
    q6, a -> q5
    q6, b -> q7
    q7, a -> q7
    q7, b -> q7
Zustandstabelle:
    q0: \{0\}
    q1: \{0,1\}
    q2: \{0,1,2\}
    q3: \{0,1,2,3\}
    q4: \emptyset
    q5: \{3\}
    q6: \{1,2\}
    q7: \{1,2,3\}

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
M ist nicht minimal, da die Zustände q3 und q7 äquivalent sind. Both accept all strings over the alphabet, as from q3, transitions on a lead to q7 and on b lead to q3, both of which are final and accept all strings, and from q7, all transitions lead to itself, which is final and accepts all strings. Therefore, they can be merged, indicating that M is not minimal.

Subproblem c (4.0/4.0P)

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

Subproblem d (2.0/2.0P)

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

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

Subproblem e (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 der folgende Algorithmus verwendet:
1. Berechne für jeden Zustand qq des DFA MM die cc-Abschlussmenge ccl(q)\text{ccl}(q), die alle Zustände enthält, die von qq aus durch beliebig viele cc-Transitionen erreichbar sind. Da MM ein DFA ist, ist die cc-Transition deterministisch, und ccl(q)\text{ccl}(q) kann durch Iteration der cc-Transitionen berechnet werden und hat höchstens nn Zustände.
2. Der DFA MM' wird durch Potenzmengenkonstruktion aus einem NFA gebildet. Die Zustände von MM' sind Teilmengen der Zustände von MM. Der Startzustand ist ccl(s)\text{ccl}(s), wobei ss der Startzustand von MM ist.
3. Für jede Zustandsmenge SQS \subseteq Q und jedes Symbol σ{a,b}\sigma \in \{a,b\} ist die Transition definiert als δ(S,σ)=qSccl(δ(q,σ))\delta'(S, \sigma) = \bigcup_{q \in S} \text{ccl}(\delta(q, \sigma)).
4. Ein Zustand SS ist final in MM', wenn SS einen Finalzustand von MM enthält.
Da die Anzahl der Teilmengen von QQ höchstens 2n2^n ist, hat MM' höchstens 2n2^n Zustände. Diese obere Schranke ist scharf, da im Worst-Case alle Teilmengen erreichbar sein können.

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 (5.0/6.0P)

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

Beweis des Falls r=r1r2r=r_1r_2:
Seien u,vΣu,v \in \Sigma^* mit u1vL(r1r2)u1v \in L(r_1 r_2). Da L(r1r2)=L(r1)L(r2)L(r_1 r_2) = L(r_1) L(r_2), existieren xL(r1)x \in L(r_1) und yL(r2)y \in L(r_2) mit u1v=xyu1v = xy.

Wir unterscheiden zwei Fälle basierend auf der Position des '1' in xyxy:

1. Fall: Das '1' ist in xx enthalten.  
   Das heißt, es existiert ein vΣv' \in \Sigma^* such that x=u1vx = u1v' und y=vy = v (da u1v=(u1v)yu1v = (u1v')y implies vy=vv' y = v, but for the prefix, we have x=u1vx = u1v' for some vv').  
   Da x=u1vL(r1)x = u1v' \in L(r_1), folgt aus der Induktionshypothese für r1r_1, dass uL(Cut(r1))u \in L(\Cut(r_1)).  
   Nach Definition ist Cut(r1r2)=Cut(r1)r1Cut(r2)\Cut(r_1 r_2) = \Cut(r_1) \mid r_1 \Cut(r_2), also L(Cut(r1r2))=L(Cut(r1))L(r1Cut(r2))L(\Cut(r_1 r_2)) = L(\Cut(r_1)) \cup L(r_1 \Cut(r_2)).  
   Da uL(Cut(r1))u \in L(\Cut(r_1)), folgt uL(Cut(r1r2))u \in L(\Cut(r_1 r_2)).

2. Fall: Das '1' ist in yy enthalten.  
   Das heißt, es existieren uΣu' \in \Sigma^* und vΣv' \in \Sigma^* such that y=u1vy = u'1v' und xu=ux u' = u (da u1v=x(u1v)u1v = x(u'1v') implies u=xuu = x u' und v=vv = v').  
   Da y=u1vL(r2)y = u'1v' \in L(r_2), folgt aus der Induktionshypothese für r2r_2, dass uL(Cut(r2))u' \in L(\Cut(r_2)).  
   Da xL(r1)x \in L(r_1) und uL(Cut(r2))u' \in L(\Cut(r_2)), ist xuL(r1Cut(r2))x u' \in L(r_1 \Cut(r_2)).  
   Nach Definition ist Cut(r1r2)=Cut(r1)r1Cut(r2)\Cut(r_1 r_2) = \Cut(r_1) \mid r_1 \Cut(r_2), also L(Cut(r1r2))=L(Cut(r1))L(r1Cut(r2))L(\Cut(r_1 r_2)) = L(\Cut(r_1)) \cup L(r_1 \Cut(r_2)).  
   Da u=xuL(r1Cut(r2))u = x u' \in L(r_1 \Cut(r_2)), folgt uL(Cut(r1r2))u \in L(\Cut(r_1 r_2)).

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

Exercise 4: CFG-Algorithmen

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

Eine CFG G=(V,Σ,P,S)G=(V,\Sigma,P,S) ist in CNF, wenn jede Produktion (Xα)P(X\rightarrow\alpha)\in P, mit 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.
S → A | B C | ε  
C → A A  
A → S D | a  
D → A E  
E → B B  
B → A S | 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.
S → AB | DE | B | D  
A → AB | a | B  
B → b | BB | D  
C → A | c  
D → BC | BS | B  
E → SS | CA | C | 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.
S → a | BA | b | SC | AA  
A → a | AA  
B → b | SC | a | AA  
C → SS | b | SC | a | AA

Subproblem e (2.0/3.0P)

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

Exercise 5: Verlorene Buchsten

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

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache Del({abbaba,baa,ab,a,b})\Del(\{abbaba,baa,ab,a,b\}) explizit auf:
Del({abbaba,baa,ab,a,b})={ε,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 Aussage ist falsch. Betrachten Sie das Gegenbeispiel L={aabb}L = \{aabb\}.

- Del(L)={vwvabw{aabb}}\Del(L) = \{vw \mid vabw \in \{aabb\}\}. Da aabbaabb nur ein Vorkommen von abab an den Positionen 2–3 hat, ist v=av = a und w=bw = b, also vw=abvw = ab. Somit Del(L)={ab}\Del(L) = \{ab\}.
- Del(Del(L))=Del({ab})={pqpabq{ab}}\Del(\Del(L)) = \Del(\{ab\}) = \{pq \mid pabq \in \{ab\}\}. Die einzige Möglichkeit ist p=ϵp = \epsilon und q=ϵq = \epsilon, also pq=ϵpq = \epsilon. Thus Del(Del(L))={ϵ}\Del(\Del(L)) = \{\epsilon\}.
- DelTwo(L)={uvwuabvabw{aabb}}\DelTwo(L) = \{uvw \mid uabvabw \in \{aabb\}\}. Da uabvabwuabvabw mindestens zwei abab-Teilwörter enthält (z.B. die fixen abab in der Definition), aber aabbaabb nur ein abab-Teilwort hat, gibt es keine u,v,wu, v, w mit uabvabw=aabbuabvabw = aabb. Somit DelTwo(L)=\DelTwo(L) = \emptyset.

Da Del(Del(L))={ϵ}=DelTwo(L)\Del(\Del(L)) = \{\epsilon\} \neq \emptyset = \DelTwo(L), gilt die Gleichheit nicht für alle endlichen Sprachen LL.

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

Produktionen PP':
- Alle Produktionen aus PP.
- Für jede Produktion XaX \to a in PP:
  - Wenn a=aa = a, dann füge XaϵX_a \to \epsilon hinzu.
  - Wenn a=ba = b, dann füge XbϵX_b \to \epsilon hinzu.
- Für jede Produktion XYZX \to Y Z in PP:
  - Füge XabYabZX_{ab} \to Y_{ab} Z hinzu.
  - Füge XabYZabX_{ab} \to Y Z_{ab} hinzu.
  - Füge XabYaZbX_{ab} \to Y_a Z_b hinzu.
  - Füge XaYZaX_a \to Y Z_a hinzu.
  - Füge XbYbZX_b \to Y_b Z hinzu.

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:
Beweis: Da L in NP ist, gibt es einen polynomialzeit Verifizierer V für L. Das heißt, für jedes Wort x existiert ein Zertifikat c, so dass V(x, c) in polynomialzeit akzeptiert genau dann wenn x ∈ L.

Um L* zu verifizieren, konstruieren wir einen Verifizierer V* wie folgt: Für ein Eingabewort w erraten wir nicht-deterministisch eine Partition von w in Teilwörter w1, w2, ..., wk (mit k ≥ 0) und für jedes wi ein Zertifikat ci. Dann überprüfen wir, dass die Konkatenation der wi gleich w ist, und dass für jedes i, V(wi, ci) akzeptiert. Da die Anzahl der Teilwörter k ≤ |w| ist und jede Verifikation V(wi, ci) in Zeit polynomial in |wi| ≤ |w| läuft, ist die Gesamtzeit von V* polynomial in |w|. Somit ist 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 gilt.

Reduktionsfunktion: Für einen gegebenen Graphen G=(V,E) G = (V, E)  für HAMILTON-PFAD, definiere einen neuen Graphen G=(V,E) G' = (V', E')  mit V=V{v} V' = V \cup \{v*\} , wobei v v*  ein neuer Knoten nicht in V V  ist, und E=E{{v,u}uV} E' = E \cup \{ \{v*, u\} \mid u \in V \} .

Angewendet auf die gegebene Instanz:
- Gegebener Graph G G : 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\} \} .
- Dann G G' : Knoten V={A,B,C,D,E,X} V' = \{A, B, C, D, E, X\}  (wobei X X  für v v*  steht).
- Kanten E={{A,B},{A,C},{B,C},{C,D},{C,E},{D,E},{X,A},{X,B},{X,C},{X,D},{X,E}} E' = \{ \{A,B\}, \{A,C\}, \{B,C\}, \{C,D\}, \{C,E\}, \{D,E\}, \{X,A\}, \{X,B\}, \{X,C\}, \{X,D\}, \{X,E\} \} .

Skizze der Korrektheit:
- Wenn G G  einen Hamilton-Pfad hat, dann existiert eine Permutation der Knoten, die alle besucht. In G G'  kann man einen Hamilton-Kreis bilden, indem man v v*  an den Anfang und das Ende des Pfades einfügt (da v v*  mit allen Knoten verbunden ist), z.B. v,v1,v2,,vn,v v*, v_1, v_2, \dotsc, v_n, v* .
- Wenn G G'  einen Hamilton-Kreis hat, muss v v*  im Kreis sein mit zwei Nachbarn u u  und w w . Entfernt man v v* , erhält man einen Hamilton-Pfad von u u  nach w w  in G G .
Daher gilt G G  hat einen Hamilton-Pfad genau dann, wenn G G'  einen Hamilton-Kreis hat.

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: CFG-LEERHEIT ist in P entscheidbar, da die Leerheit einer kontextfreien Grammatik in polynomieller Zeit überprüft werden kann, beispielsweise durch Analyse der Erreichbarkeit und Produktivität von Symbolen. 3KNF-SAT ist NP-vollständig. Unter der Annahme P ≠ NP kann 3KNF-SAT nicht in P liegen. Wenn 3KNF-SAT ≤p CFG-LEERHEIT gelten würde, dann folgt aus CFG-LEERHEIT ∈ P, dass 3KNF-SAT ∈ P, was ein Widerspruch zu P ≠ NP ist. Daher ist die Reduktion nicht möglich.

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 gilt.

Reduktionsfunktion: Gegeben eine Instanz von EXAKTE-ÜBERDECKUNG mit Menge M={m1,,mk} M = \{m_1, \dotsc, m_k\}  und Teilmengen T={T1,,Tn} T = \{T_1, \dotsc, T_n\} , wird eine CNF-Formel für SAT wie folgt konstruiert:
- Für jede Teilmenge Ti T_i  wird eine boolesche Variable xi x_i  eingeführt, die wahr ist, wenn Ti T_i  in der exakten Überdeckung enthalten ist.
- Für jedes Element mM m \in M :
  - Sei Cm={imTi} C_m = \{ i \mid m \in T_i \}  die Menge der Indizes von Teilmengen, die m m  enthalten.
  - Füge eine Klausel hinzu: iCmxi \bigvee_{i \in C_m} x_i  (stellt sicher, dass m m  mindestens einmal covered wird).
  - Für jedes Paar i,jCm i, j \in C_m  mit i<j i < j , füge eine Klausel hinzu: ¬xi¬xj \neg x_i \lor \neg x_j  (stellt sicher, dass m m  höchstens einmal covered wird).

Die SAT-Formel ist die Konjunktion aller dieser Klauseln.

Angewendet auf die gegebene Instanz:
- 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: x1,x2,x3,x4,x5 x_1, x_2, x_3, x_4, x_5  für T1,T2,T3,T4,T5 T_1, T_2, T_3, T_4, T_5 

Klauseln für jedes Element:
- Element 1: C1={1,2,3} C_1 = \{1,2,3\}  → Klauseln: x1x2x3 x_1 \lor x_2 \lor x_3 , ¬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 
- Element 2: C2={3,4} C_2 = \{3,4\}  → Klauseln: x3x4 x_3 \lor x_4 , ¬x3¬x4 \neg x_3 \lor \neg x_4 
- Element 3: C3={2,3} C_3 = \{2,3\}  → Klauseln: x2x3 x_2 \lor x_3 , ¬x2¬x3 \neg x_2 \lor \neg x_3 
- Element 4: C4={4} C_4 = \{4\}  → Klausel: x4 x_4 

Die vollständige SAT-Formel ist:
(x1x2x3)(¬x1¬x2)(¬x1¬x3)(¬x2¬x3)(x3x4)(¬x3¬x4)(x2x3)(¬x2¬x3)(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 (\neg x_2 \lor \neg x_3) \land (x_4)


Skizze der Korrektheit: Die Formel ist genau dann erfüllbar, wenn es eine Auswahl von Teilmengen gibt, die jedes Element genau einmal covered. Die Klauseln garantieren, dass für jedes Element mindestens eine und höchstens eine Teilmenge, die es enthält, ausgewählt ist.

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:
Angenommen, die Sprache L = { a^i b^j c^k : (i ≠ 1 ∨ j = k) ∧ i,j,k ≥ 0 } sei regulär. Betrachte die reguläre Sprache R = { a b^j c^k : j,k ≥ 0 }. Da reguläre Sprachen unter Schnitt abgeschlossen sind, müsste L ∩ R regulär sein.

Es gilt: L ∩ R = { a b^j c^k : (i ≠ 1 ∨ j = k) ∧ i = 1 } = { a b^j c^k : j = k } = { a b^j c^j : j ≥ 0 }.

Diese Sprache ist nicht regulär. Zum Beweis verwenden wir das Pumping-Lemma: Angenommen, { a b^j c^j : j ≥ 0 } sei regulär. Sei p die Pumping-Länge. Betrachte das Wort s = a b^p c^p. Nach dem Pumping-Lemma kann s in xyz zerlegt werden mit |xy| ≤ p, |y| > 0, und für alle i ≥ 0 gilt xy^i z ∈ { a b^j c^j : j ≥ 0 }.

Da |xy| ≤ p und s mit a beginnt, gefolgt von b's, besteht y nur aus b's. Dann ist für i = 0 das Wort xy^0 z = a b^{p-|y|} c^p. Da |y| > 0, ist p - |y| < p, also die Anzahl der b's ungleich der Anzahl der c's, somit xy^0 z nicht in { a b^j c^j : j ≥ 0 }, Widerspruch.

Daher ist L ∩ R nicht regulär, was der Annahme widerspricht, dass L regulär ist. Also ist L 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: baa

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Angenommen, die Sprache L={wΣ:L(Mw)2=25} L = \{ w \in \Sigma^* : |L(M_w)|^2 = 25 \}  sei entscheidbar. Da L(Mw)2=25 |L(M_w)|^2 = 25  genau dann gilt, wenn L(Mw)=5 |L(M_w)| = 5 , ist L L  äquivalent zu {w:L(Mw)=5} \{ w : |L(M_w)| = 5 \} .

Wir reduzieren das Halteproblem auf L L . Das Halteproblem H={M,x:M ha¨lt auf Eingabe x} H = \{ \langle M, x \rangle : M \text{ hält auf Eingabe } x \}  ist unentscheidbar.

Für eine gegebene Turingmaschine M M  und Eingabe x x  konstruieren wir eine Turingmaschine M M'  wie folgt: M M'  ignoriert ihre eigene Eingabe y y  und simuliert zunächst M M  auf x x . Wenn M M  auf x x  hält, dann akzeptiert M M'  genau dann, wenn y y  zu einer festen Menge von fünf Strings gehört, z.B. S={ε,0,1,00,01} S = \{ \varepsilon, 0, 1, 00, 01 \} . Wenn M M  auf x x  nicht hält, dann hält M M'  nie, also akzeptiert sie keine Strings.

Somit gilt:
- Wenn M M  auf x x  hält, dann L(M)=S L(M') = S , also L(M)=5 |L(M')| = 5 .
- Wenn M M  auf x x  nicht hält, dann L(M)= L(M') = \emptyset , also L(M)=05 |L(M')| = 0 \neq 5 .

Daher hält M M  auf x x  genau dann, wenn L(M)=5 |L(M')| = 5 .

Wenn L L  entscheidbar wäre, könnten wir für jedes M,x \langle M, x \rangle  die Maschine M M'  konstruieren und entscheiden, ob L(M)=5 |L(M')| = 5 , und somit das Halteproblem entscheiden. Dies ist ein Widerspruch, da H H  unentscheidbar ist. Also ist L L  unentscheidbar.