Exam 2024_retake.txt — anthropic/claude-opus-4.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 2.0/3.0 3.0/3.0 15.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 0.0/2.0 1.0/1.0 2.0/2.0 3.0/5.0
Exam total 101.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 (2.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=ab(aba)X=ab(a^*b^*a)^*
Y=((ba)abb)Y=((b|a)a^* | bb)^*
Z=Z=\emptyset
0: wrong language: contains aba

Subproblem g (3.0/3.0P)

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

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

Da aaL(N)aa \in L(N), existiert ein akzeptierender Pfad q0ap1ap2q_0 \xrightarrow{a} p_1 \xrightarrow{a} p_2 mit p2Fp_2 \in F.

Da bbL(N)bb \in L(N), existiert ein akzeptierender Pfad q0br1br2q_0 \xrightarrow{b} r_1 \xrightarrow{b} r_2 mit r2Fr_2 \in F.

Aus der Reversibilität folgt:
- Da p1δ(q0,a)p_1 \in \delta(q_0, a), gilt q0δ(p1,a)q_0 \in \delta(p_1, a)
- Da r1δ(q0,b)r_1 \in \delta(q_0, b), gilt q0δ(r1,b)q_0 \in \delta(r_1, b)  
- Da r2δ(r1,b)r_2 \in \delta(r_1, b), gilt r1δ(r2,b)r_1 \in \delta(r_2, b)

Somit gilt δ(r1,b){q0,r2}\delta(r_1, b) \supseteq \{q_0, r_2\}.

Betrachte den Pfad: q0br1bq0ap1ap2q_0 \xrightarrow{b} r_1 \xrightarrow{b} q_0 \xrightarrow{a} p_1 \xrightarrow{a} p_2

Dieser Pfad entspricht dem Wort bbaabbaa und endet im akzeptierenden Zustand p2p_2. Also gilt bbaaL(N)bbaa \in L(N).

Aber bbaa(aa)(bb)bbaa \notin (aa)^*(bb)^*, da in (aa)(bb)(aa)^*(bb)^* alle aa's vor allen bb's kommen müssen. Widerspruch!

Daher existiert kein reversibler NFA für (aa)(bb)(aa)^*(bb)^*.

Exercise 2: DFA-Algorithmen


Subproblem a (6.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, b -> q3
    q2, a -> q5
    q3, b -> q3
    q3, a -> q7
    q7, a -> q7
    q7, b -> q7
    q5, b -> q4
    q5, a -> q6
    q6, a -> q5
    q6, b -> q7
    q4, a -> q4
    q4, b -> q4
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 0, 1, 2, 3
    q4: \emptyset
    q5: 3
    q6: 1, 2
    q7: 1, 2, 3

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
M ist nicht minimal. Die Zustände q2 und q6 sind äquivalent, da sie beide auf 'a' nach q5 gehen und auf 'b' zu äquivalenten Zuständen (q3 bzw. q7) übergehen. Ebenso sind q3 und q7 äquivalent, da beide auf 'a' nach q7 gehen und auf 'b' Selbstschleifen haben (q3→q3 bzw. q7→q7). Diese Paare von äquivalenten Zuständen können jeweils zu einem Zustand verschmolzen werden, wodurch ein minimaler DFA mit 6 statt 8 Zuständen entsteht.

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:
Algorithmus zur Konstruktion von MM':

Gegeben sei ein DFA M=(Q,{a,b,c},δ,q0,F)M = (Q, \{a,b,c\}, \delta, q_0, F) mit nn Zuständen.

1. Konstruiere einen NFA mit ε\varepsilon-Transitionen: Erstelle einen NFA N=(Q,{a,b},δ,q0,F)N = (Q, \{a,b\}, \delta', q_0, F) mit:
   - Denselben Zuständen wie MM
   - Für jede Transition δ(q,a)=q\delta(q, a) = q' mit a{a,b}a \in \{a,b\}: füge (q,a,q)(q, a, q') zu δ\delta' hinzu
   - Für jede Transition δ(q,c)=q\delta(q, c) = q': füge (q,ε,q)(q, \varepsilon, q') zu δ\delta' hinzu

2. Entferne ε\varepsilon-Transitionen: Berechne für jeden Zustand qq die ε\varepsilon-Hülle ε-closure(q)\varepsilon\text{-closure}(q). Erstelle einen NFA ohne ε\varepsilon-Transitionen, indem für jede Transition (q,a,p)(q, a, p) mit a{a,b}a \in \{a,b\} und jeden Zustand rε-closure(p)r \in \varepsilon\text{-closure}(p) eine Transition (q,a,r)(q, a, r) hinzugefügt wird. Die Finalzustände sind alle Zustände qq, deren ε\varepsilon-Hülle mindestens einen ursprünglichen Finalzustand enthält.

3. Potenzmengenkonstruktion: Konvertiere den resultierenden NFA zu einem DFA MM' mittels Potenzmengenkonstruktion.

Begründung für die Schranke f(n)=2nf(n) = 2^n:

Der konstruierte NFA hat dieselben nn Zustände wie der ursprüngliche DFA MM. Bei der Potenzmengenkonstruktion entspricht jeder Zustand des resultierenden DFA einer Teilmenge der NFA-Zustände. Da es maximal 2n2^n verschiedene Teilmengen von nn Zuständen gibt, hat der resultierende DFA MM' höchstens 2n2^n Zustände.

Die Korrektheit folgt daraus, dass ein Wort w{a,b}w \in \{a,b\}^* genau dann von MM' akzeptiert wird, wenn es ein Wort v{a,b,c}v \in \{a,b,c\}^* gibt mit w=Rc(v)w = R_c(v) und vL(M)v \in L(M).

Exercise 3: Rekursive Funktionen

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

Subproblem a (1.0/1.0P)

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

Subproblem b (6.0/6.0P)

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

Subproblem c (6.0/6.0P)

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

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

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

Zu zeigen: Für alle u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall $r=r_1r_2$:
- **(IH1):** Für alle $u1v \in L(r_1)$ mit $u,v \in \Sigma^*$ gilt $u \in L(\Cut(r_1))$.
- **(IH2):** Für alle $u1v \in L(r_2)$ mit $u,v \in \Sigma^*$ gilt $u \in L(\Cut(r_2))$.

Beweis des Falls $r=r_1r_2$:
Sei $u1v \in L(r_1r_2)$ mit $u,v \in \Sigma^*$ beliebig gewählt. Da $u1v \in L(r_1r_2)$, existieren Wörter $w_1 \in L(r_1)$ und $w_2 \in L(r_2)$ mit $u1v = w_1w_2$.

Wir unterscheiden zwei Fälle, je nachdem wo die '1' in der Konkatenation $w_1w_2$ auftritt:

**Fall 1:** Die '1' befindet sich innerhalb von $w_1$ (d.h. $|u| + 1 \leq |w_1|$).
Dann können wir $w_1 = u1v'$ für ein $v' \in \Sigma^*$ schreiben, wobei $v = v'w_2$.
Da $u1v' = w_1 \in L(r_1)$, folgt aus **(IH1)**, dass $u \in L(\Cut(r_1))$.
Da $\Cut(r_1r_2) = \Cut(r_1) \mid r_1\Cut(r_2)$, gilt $u \in L(\Cut(r_1r_2))$.

**Fall 2:** Die '1' befindet sich innerhalb von $w_2$ (d.h. $|u| + 1 > |w_1|$).
Sei $u_2$ das Präfix von $w_2$ der Länge $|u| - |w_1|$, sodass $u = w_1u_2$.
Dann gilt $w_2 = u_21v_2$ für ein $v_2 \in \Sigma^*$ mit $v = v_2$.
Da $u_21v_2 = w_2 \in L(r_2)$, folgt aus **(IH2)**, dass $u_2 \in L(\Cut(r_2))$.
Daher gilt $u = w_1u_2 \in L(r_1\Cut(r_2))$.
Da $\Cut(r_1r_2) = \Cut(r_1) \mid r_1\Cut(r_2)$, gilt $u \in L(\Cut(r_1r_2))$.

In beiden Fällen haben wir gezeigt, dass $u \in 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 XVX\in V und α(ΣV)\alpha\in(\Sigma\cup V)^*, folgende Bedingungen erfüllt:
(1) αΣV\alpha\in\Sigma\cup V^*; Terminale dürfen nur in Produktionen der Länge 1 erzeugt werden.
(2) α2|\alpha|\le2; jede Produktion hat höchstens Länge 22.
(3) αε\alpha\ne\varepsilon; es gibt keine ε\varepsilon-Produktionen.
(4) αV\alpha\notin V; es gibt keine Kettenproduktionen.

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

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

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

\paragraph{Konstruktion einer Chomsky-Normalform}

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

Subproblem a (2.0/2.0P)

Entfernen von Terminalen in langen Produktionen. Die CFG GaG_a ist gegeben durch folgende Produktionen:
SaXXaabS \rightarrow aX \mid Xa \mid ab
XSSSεbXXX \rightarrow SS \mid S \mid \varepsilon \mid bXX
Führen Sie den ersten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG GaG'_a an, so dass L(Ga)=L(Ga)L(G_a) = L(G'_a) gilt und GaG'_a Bedingung (1) erfüllt.
SAaXXAaAaAbS \rightarrow A_aX \mid XA_a \mid A_aA_b
XSSSεAbXXX \rightarrow SS \mid S \mid \varepsilon \mid A_bXX
AaaA_a \rightarrow a
AbbA_b \rightarrow b

Subproblem b (2.0/2.0P)

Entfernen langer Produktionen. Die CFG GbG_b ist gegeben durch die folgenden Produktionen:
SABAAεS \rightarrow A \mid BAA \mid \varepsilon
ASABBaA \rightarrow SABB \mid a
BASbB \rightarrow AS \mid b
Führen Sie den zweiten Schritt des Algorithmus zur Überführung in CNF aus und geben Sie die Produktionen einer CFG GbG'_b an, so dass L(Gb)=L(Gb)L(G_b) = L(G'_b) und GbG'_b Bedingungen (1) und (2) erfüllt.
SABC1εS \rightarrow A \mid BC_1 \mid \varepsilon
ASC2aA \rightarrow SC_2 \mid a
BASbB \rightarrow AS \mid b
C1AAC_1 \rightarrow AA
C2AC3C_2 \rightarrow AC_3
C3BBC_3 \rightarrow BB

Subproblem c (3.0/3.0P)

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

The word aabbaabb contains exactly one occurrence of the substring abab (at positions 1-2).

Computing Del(Del(L))\Del(\Del(L)):
- Del({aabb})={ab}\Del(\{aabb\}) = \{ab\} (removing the abab from aabba\underline{ab}b gives abab)
- Del({ab})={ε}\Del(\{ab\}) = \{\varepsilon\} (removing abab from abab gives the empty word)
- Therefore: Del(Del({aabb}))={ε}\Del(\Del(\{aabb\})) = \{\varepsilon\}

Computing DelTwo(L)\DelTwo(L):
- DelTwo(L)\DelTwo(L) consists of words obtained by removing exactly two occurrences of abab from words in LL
- Since aabbaabb contains only one occurrence of abab, we cannot remove two occurrences
- Therefore: DelTwo({aabb})=\DelTwo(\{aabb\}) = \emptyset

Since Del(Del({aabb}))={ε}=DelTwo({aabb})\Del(\Del(\{aabb\})) = \{\varepsilon\} \neq \emptyset = \DelTwo(\{aabb\}), the statement is false.

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':

Für jede Produktion XYZPX \rightarrow YZ \in P:
- XYZX \rightarrow YZ
- XabYabZX_{ab} \rightarrow Y_{ab}Z
- XabYZabX_{ab} \rightarrow YZ_{ab}
- XabYaZbX_{ab} \rightarrow Y_a Z_b
- XaYZaX_a \rightarrow YZ_a
- XbYbZX_b \rightarrow Y_b Z

Für jede Produktion XaPX \rightarrow a \in P:
- XaX \rightarrow a
- XaεX_a \rightarrow \varepsilon

Für jede Produktion XbPX \rightarrow b \in P:
- XbX \rightarrow b
- XbεX_b \rightarrow \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:
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 SA_{ab}\mid S_a A_b
SaSAaεS_a\rightarrow SA_a\mid\varepsilon
SbSbAS_b\rightarrow S_b A
AabA\rightarrow a\mid b
AabA_{ab}\rightarrow 
AaεA_a\rightarrow \varepsilon
AbεA_b\rightarrow \varepsilon
0 mistakes

Exercise 6: Quiz: Berechenbarkeit und Komplexität

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

Subproblem a (2.0/2.0P)

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
LL ist entscheidbarL\overline{L} ist entscheidbarLL ist semi-entscheidbar

Subproblem b (2.0/2.0P)

Seien L1,L2ΣL_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
L1L2L_1\cap L_2L1L2L_1\setminus L_2L1L2L_1L_2

Subproblem c (2.0/2.0P)

Sei L{0}L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:NNf:\N\rightarrow\N sind berechenbar?
f(n):=LΣnf(n):=|L\cap \Sigma^n|f(n):=min{kN:0kL}f(n):=\min\{k\in\N: 0^k\in L\}f(n):=1f(n):=1, falls 0nL0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P)

Seien A,BΣA,B\subseteq\Sigma^* Sprachen mit ApSATpBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
ANPA\in\NPBNPB\in\NPBB ist NP-hartApBA\le_p B

Subproblem e (2.0/2.0P)

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

Subproblem f (4.0/4.0P)

Sei LNPL\in\NP. Zeigen oder widerlegen Sie: LNPL^*\in\NP.
Ja, Beweis:Nein, Gegenbeispiel:
Sei LNPL \in \mathsf{NP} mit Verifizierer VV und Zertifikatslänge polynomial beschränkt durch p(n)p(n) für Eingaben der Länge nn.

Wir zeigen LNPL^* \in \mathsf{NP} durch Angabe eines Verifizierers:

Zertifikat für wLw \in L^*:
- Eine Zerlegung w=w1w2wkw = w_1 w_2 \ldots w_k mit wiLw_i \in L für alle ii
- Für jedes wiw_i ein Zertifikat cic_i mit cip(wi)|c_i| \leq p(|w_i|), das bezeugt, dass wiLw_i \in L

Verifizierer für LL^*:
Bei Eingabe ww und Zertifikat (w1,,wk,c1,,ck)(w_1, \ldots, w_k, c_1, \ldots, c_k):
1. Prüfe ob w=w1w2wkw = w_1 w_2 \ldots w_k
2. Für jedes i{1,,k}i \in \{1, \ldots, k\}: Prüfe ob V(wi,ci)=1V(w_i, c_i) = 1
3. Akzeptiere genau dann, wenn alle Prüfungen erfolgreich sind

Polynomialität:
- Es gilt kwk \leq |w| und wiw|w_i| \leq |w| für alle ii
- Die Gesamtlänge des Zertifikats ist O(wp(w))O(|w| \cdot p(|w|)), also polynomial in w|w|
- Die Laufzeit ist polynomial, da wir höchstens w|w| mal den Verifizierer VV aufrufen

Daher gilt LNPL^* \in \mathsf{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
Reduktionsfunktion: Gegeben ein Graph G=(V,E)G = (V, E), konstruiere G=(V,E)G' = (V', E') mit:
- V=V{x}V' = V \cup \{x\} (füge einen neuen Knoten xVx \notin V hinzu)
- E=E{{x,v}vV}E' = E \cup \{\{x, v\} \mid v \in V\} (verbinde xx mit allen ursprünglichen Knoten)

Anwendung auf die gegebene Instanz:
Der transformierte Graph GG' hat:
- Knoten: A, B, C, D, E, x
- Kanten: A--B, A--C, B--C, C--D, C--E, D--E, x--A, x--B, x--C, x--D, x--E

Korrektheitsskizze: 
GG hat einen Hamilton-Pfad \Leftrightarrow GG' hat einen Hamilton-Kreis, da:
- Vorwärts: Ein Hamilton-Pfad v1,,vnv_1, \ldots, v_n in GG wird zu einem Hamilton-Kreis x,v1,,vn,xx, v_1, \ldots, v_n, x in GG'
- Rückwärts: Jeder Hamilton-Kreis in GG' muss xx enthalten, und das Entfernen von xx liefert einen Hamilton-Pfad in GG

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
Beweis, dass die Aussage nicht gilt:

CFG-LEERHEIT ist in P, da es einen Polynomialzeit-Algorithmus gibt, der die produktiven Nichtterminale einer kontextfreien Grammatik berechnet und prüft, ob das Startsymbol produktiv ist. Eine Grammatik erzeugt genau dann die leere Sprache, wenn ihr Startsymbol nicht produktiv ist.

3KNF-SAT ist NP-vollständig.

Annahme: Es gäbe eine Polynomialzeit-Reduktion 3KNF-SAT p\leq_p CFG-LEERHEIT.

Folgerung: Dann könnten wir 3KNF-SAT in Polynomialzeit lösen:
- Gegeben eine 3KNF-Formel φ, wende die Reduktion an und erhalte eine CFG G
- Teste in Polynomialzeit, ob L(G) = ∅
- Dies liefert die Antwort für die Erfüllbarkeit von φ

Das würde bedeuten 3KNF-SAT ∈ P, also P = NP, was unserer Annahme P ≠ NP widerspricht.

Konklusion: Die Reduktion 3KNF-SAT p\leq_p CFG-LEERHEIT kann unter der Annahme P ≠ NP nicht existieren.

Subproblem c (7.0/7.0P)

EXAKTE-ÜBERDECKUNG ist das folgende Entscheidungsproblem:

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

Ausgabe: Enthält TT eine exakte Überdeckung von MM, d.h. gibt es eine Menge 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 (M,T)(M, T) mit M={m1,,mk}M = \{m_1, \ldots, m_k\} und T={T1,,Tn}T = \{T_1, \ldots, T_n\}:
- Variablen: Für jedes TiT_i eine Variable xix_i (wahr gdw. TiT_i in der Überdeckung)
- Formel: Für jedes mjMm_j \in M mit Ij={imjTi}I_j = \{i \mid m_j \in T_i\}:
  - Mindestens eine Überdeckung: iIjxi\bigvee_{i \in I_j} x_i
  - Höchstens eine Überdeckung: i1<i2,i1,i2Ij(¬xi1¬xi2)\bigwedge_{i_1 < i_2, i_1,i_2 \in I_j} (\neg x_{i_1} \vee \neg x_{i_2})

Anwendung auf die gegebene Instanz:
Variablen: x1,x2,x3,x4,x5x_1, x_2, x_3, x_4, x_5

Für Element 1 (in T1,T2,T3T_1, T_2, T_3):
(x1x2x3)(¬x1¬x2)(¬x1¬x3)(¬x2¬x3)(x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3)

Für Element 2 (in T3,T4T_3, T_4):
(x3x4)(¬x3¬x4)(x_3 \vee x_4) \wedge (\neg x_3 \vee \neg x_4)

Für Element 3 (in T2,T3T_2, T_3):
(x2x3)(¬x2¬x3)(x_2 \vee x_3) \wedge (\neg x_2 \vee \neg x_3)

Für Element 4 (in T4T_4):
x4x_4

Resultierende Formel:
ϕ=(x1x2x3)(¬x1¬x2)(¬x1¬x3)(¬x2¬x3)(x3x4)(¬x3¬x4)(x2x3)(¬x2¬x3)x4\phi = (x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge (x_3 \vee x_4) \wedge (\neg x_3 \vee \neg x_4) \wedge (x_2 \vee x_3) \wedge (\neg x_2 \vee \neg x_3) \wedge x_4

Korrektheitsskizze: Eine exakte Überdeckung existiert gdw. ϕ\phi erfüllbar ist. Die Belegung xi=x_i =  wahr entspricht der Auswahl von TiT_i.

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (0.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={aibjck:(i1j=k)i,j,k0}L = \{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\} ist regulär. Dann existiert eine Pumping-Länge pp.

Betrachte den String w=abpcpw = ab^pc^p. Es gilt w=1+2pp|w| = 1 + 2p \ge p und wLw \in L, da i=1i=1 und j=k=pj=k=p, also die Bedingung (i1j=k)(i\ne 1\vee j=k) erfüllt ist.

Nach dem Pumping-Lemma kann w=xyzw = xyz geschrieben werden mit:
1. xyp|xy| \le p
2. y>0|y| > 0  
3. Für alle n0n \ge 0 gilt xynzLxy^nz \in L

Da xyp|xy| \le p und der String mit aa beginnt gefolgt von pp b's, besteht xyxy aus dem aa und höchstens p1p-1 b's.

Da y>0|y| > 0 und yy ein Teilstring von xyxy ist, muss y=bmy = b^m für ein m>0m > 0 gelten (da wir nur ein aa haben und xyp|xy| \le p).

Dann ist x=ax = a und z=bpmcpz = b^{p-m}c^p.

Für n=0n = 0 erhalten wir:
xy0z=abpmcpxy^0z = ab^{p-m}c^p

Dieser String hat i=1i=1, j=pmj=p-m und k=pk=p. Damit er in LL ist, muss (11pm=p)(1\ne 1\vee p-m=p) gelten, was zu pm=pp-m=p führt. Dies ist falsch, da m>0m > 0.

Also ist xy0zLxy^0z \notin L, was dem Pumping-Lemma widerspricht.

Daher 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: baba
2: -
3: baabaa

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:
Wir zeigen, dass L1={wΣ:L(Mw)2=25}L_1 = \{w\in\Sigma^*:|L(M_w)|^2=25\} unentscheidbar ist mittels Rice's Theorem.

Die Sprache L1L_1 entspricht der Menge aller Turingmaschinen-Kodierungen, deren akzeptierte Sprache genau 5 Elemente enthält (da L(Mw)2=25L(Mw)=5|L(M_w)|^2 = 25 \Rightarrow |L(M_w)| = 5).

Nach Rice's Theorem ist jede nicht-triviale Eigenschaft von Sprachen, die von Turingmaschinen erkannt werden, unentscheidbar. Eine Eigenschaft PP ist nicht-trivial, wenn:
1. Es mindestens eine Turingmaschine gibt, deren Sprache die Eigenschaft PP hat
2. Es mindestens eine Turingmaschine gibt, deren Sprache die Eigenschaft PP nicht hat

Für die Eigenschaft "L=5|L| = 5":
1. Existenz einer TM mit der Eigenschaft: Konstruiere eine TM M1M_1, die genau die Strings {0,1,00,01,10}\{0, 1, 00, 01, 10\} akzeptiert. Diese TM prüft einfach, ob die Eingabe einem dieser 5 Strings entspricht und akzeptiert genau dann. Also gilt L(M1)=5|L(M_1)| = 5.

2. Existenz einer TM ohne die Eigenschaft: Konstruiere eine TM M2M_2, die alle Strings akzeptiert (d.h. L(M2)=ΣL(M_2) = \Sigma^*). Da Σ\Sigma^* unendlich ist, gilt L(M2)=5|L(M_2)| = \infty \ne 5.

Da die Eigenschaft "L=5|L| = 5" nicht-trivial ist, folgt aus Rice's Theorem, dass L1={wΣ:L(Mw)2=25}L_1 = \{w\in\Sigma^*:|L(M_w)|^2=25\} unentscheidbar ist.