Exam 2024_endterm.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 3.0/3.0 3.0/3.0 16.0/16.0
2: Residualsprachen und Minimierung 3.0/5.0 2.0/2.0 2.0/2.0 2.0/2.0 3.0/3.0 4.0/4.0 16.0/18.0
3: NFA-Konstruktion 3.0/3.0 7.0/7.0 3.0/3.0 13.0/13.0
4: NFA zu regulärem Ausdruck 9.0/9.0 3.0/3.0 12.0/12.0
5: Kontextfreie Sprachen 4.0/6.0 4.0/4.0 3.0/3.0 11.0/13.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 6.0/6.0 8.0/8.0 14.0/14.0
8: Bonus 2.0/2.0 0.0/1.0 2.0/2.0 4.0/5.0
Exam total 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.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P)

Sei LΣL\subseteq\Sigma^* eine endliche Sprache mit L=L|L|=|L^*|. Welche Aussagen sind wahr?
LL ist regulärεL\varepsilon\in LL=LL|L|=|LL|

Subproblem b (2.0/2.0P)

Sei LΣL\subseteq\Sigma^* und L:={wL:w210w}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
LL' ist regulärLL' ist kontextfreiLL' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P)

Sei LΣL\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
{wL:w0(modk)}\{w\in L: |w| \equiv 0\pmod k\}{w1...wk:w1,...,wkL}\{w_1...w_k: w_1,...,w_k\in L\}{wk:wL}\{w^k: w\in L\}

Subproblem d (2.0/2.0P)

Sei LΣL\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xkLx1,...,xkΣk0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
L\overline{L}LLRL\cup L^RLLRL\cap L^R

Subproblem e (2.0/2.0P)

Sei GG die Grammatik mit Produktionen SaTS\rightarrow aT, TSbT\rightarrow Sb. Welche Aussagen sind wahr?
GG ist rechtslinearGG ist kontextfreiL(G)L(G) ist regulärL(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P)

Seien L1,L2,L3{a,b}L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babbL3\varepsilon,ab,babb\in L_3 und b,ba,aabbL3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i{1,2,3}i\in\{1,2,3\}.
r1=((ab)(ab))r_1=((a|b)(a|b))^*
r2=(abb)r_2=(ab|b)^*
r3=(abb(ab)b)r_3=(ab|b(ab)^*b)^*

Subproblem g (3.0/3.0P)

Sei MM der folgende DFA. Gibt es einen DFA MM', sodass L(M)L(M) und L(M)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:wΣ}={L(M)w:wΣ}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)L(M)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
Wahr, DFAFalsch, Begründung
M':
- Zustände: 0, 1, 2
- Startzustand: 2 (statt 0)
- Finalzustände: 2
- Transitionen: (gleich wie M)
  - 0, a → 1
  - 0, b → 2
  - 1, a → 0
  - 1, b → 2
  - 2, a → 0
  - 2, b → 2

Dann gilt L(M') = {ε} ∪ Σb ≠ Σb = L(M), aber beide haben dieselben Residualsprachen {Σb, {ε} ∪ Σb}.

Exercise 2: Residualsprachen und Minimierung


Subproblem a (3.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): bb
(0,4): bb
(0,5): ε\varepsilon
(1,2): aa
(1,3): bb
(1,4): bb
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon
4 wrong words (-2P)

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={qQ:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Aus der Äquivalenztabelle ergibt sich die Menge SS durch Identifikation der Zustände, die in keinem Paar mit einem anderen Zustand äquivalent sind. In der Tabelle sehen wir, dass nur die Paare (0,1) und (3,4) mit "==" markiert sind. Das bedeutet:
- Zustände 0 und 1 sind zueinander äquivalent, also [0]M=[1]M={0,1}[0]_M = [1]_M = \{0,1\}
- Zustände 3 und 4 sind zueinander äquivalent, also [3]M=[4]M={3,4}[3]_M = [4]_M = \{3,4\}
- Zustand 2 hat kein "==" in seiner Zeile/Spalte, ist also nur zu sich selbst äquivalent: [2]M={2}[2]_M = \{2\}
- Zustand 5 hat kein "==" in seiner Zeile/Spalte, ist also nur zu sich selbst äquivalent: [5]M={5}[5]_M = \{5\}

Daher enthält SS genau die Zustände 2 und 5.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA MM':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von MM' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w{a,b}}{a,b,c}L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^na^n\}
Lcban=L^{cba^n}=\emptyset
Lan={ucuRan:u{a,b}}L^{a^n}=\{ucu^Ra^n : u \in \{a,b\}^*\}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\in\N ein Wort wn{a,b}w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Sei i,jNi,j \in \mathbb{N} mit iji \neq j. Wir zeigen, dass LaiLajL^{a^i} \neq L^{a^j}.

Betrachte das Wort bib^i. Wir zeigen, dass biLajb^i \in L^{a^j} aber biLaib^i \notin L^{a^i}.

Behauptung 1: biLaib^i \notin L^{a^i}
Damit biLaib^i \in L^{a^i} gilt, müsste aibiLa^ib^i \in L gelten. Da L={anbm:n,m0nm}L = \{a^nb^m : n,m \geq 0 \land n \neq m\} und hier n=i=mn = i = m, gilt aibiLa^ib^i \notin L. Also ist biLaib^i \notin L^{a^i}.

Behauptung 2: biLajb^i \in L^{a^j} (für iji \neq j)
Damit biLajb^i \in L^{a^j} gilt, muss ajbiLa^jb^i \in L gelten. Da jij \neq i, ist die Bedingung nmn \neq m in der Definition von LL erfüllt, und somit gilt ajbiLa^jb^i \in L. Also ist biLajb^i \in L^{a^j}.

Da bib^i in LajL^{a^j} enthalten ist, aber nicht in LaiL^{a^i}, folgt LaiLajL^{a^i} \neq L^{a^j}.

Dies zeigt, dass alle Residualsprachen Lw0,Lw1,Lw2,...L^{w_0}, L^{w_1}, L^{w_2}, ... paarweise verschieden sind. Da es unendlich viele verschiedene Residualsprachen gibt, ist LL nach dem Satz von Myhill-Nerode nicht regulär.

Exercise 3: NFA-Konstruktion

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache LΣL\subseteq\Sigma^* bezeichnet L0L^{\downarrow 0} die Sprache, die man erhält, wenn man den Wörtern aus LL jeweils genau zwei Nullen entfernt. Z.B. gilt {0,010,1}0={1}\{0,010, 1\}^{\downarrow 0}=\{1\} und {1,101,0}0=\{1,101, 0\}^{\downarrow 0}=\emptyset. Formal:
L0:={uvw:u0v0wLu,v,wΣ}L^{\downarrow 0}:= \{uvw: u0v0w\in L \wedge u,v,w\in\Sigma^*\}
Beachten Sie insbesondere, dass das Löschen nicht optional ist.

Subproblem a (3.0/3.0P)

Gegeben sind drei reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 über Σ\Sigma. Geben Sie jeweils reguläre Ausdrücke s1,s2,s3s_1,s_2,s_3 an, sodass L(si)=L(ri)0L(s_i)=L(r_i)^{\downarrow 0} für i{1,2,3}i\in\{1,2,3\}.
r1:=(01)(01)r_1:=(0\mid 1)(0\mid 1), s1=εs_1=\varepsilon
r2:=(01)r_2:=(0\mid 1)^*, s2=(01)s_2=(0\mid 1)^*
r3:=(01)r_3:=(01)^*, s3=(01)1(01)1(01)s_3=(01)^*1(01)^*1(01)^*

Subproblem b (7.0/7.0P)

Sei M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F) ein beliebiger NFA. Es gilt weiterhin Σ={0,1}\Sigma=\{0,1\}. Konstruieren Sie einen ϵ\epsilon-NFA M=(Q,Σ,δ,q0,F)M'=(Q',\Sigma,\delta',q_0',F') mit L(M)=L(M)0L(M')=L(M)^{\downarrow 0}, indem Sie QQ', q0q_0', FF', und δ\delta' präzise angeben.

Sie können (müssen aber nicht) zusätzlich die Idee hinter Ihrer Konstruktion erläutern. Dies kann uns helfen, Ihre Definitionen zu verstehen.

Wenden Sie anschließend Ihre Konstruktion auf den nachfolgenden NFA M1M_1 an und zeichnen Sie das Ergebnis.

Hinweis: Sie können δ\delta' in Form von Gleichungen „δ(q,x):={...}\delta'(q',x):=\{...\}" oder alternativ Mengen von Tripeln „{(q,x,p)...}\{(q',x,p')\mid...\}" mit q,pQ,xΣ{ϵ}q',p'\in Q',x\in\Sigma\cup\{\epsilon\} angeben.
NFA M1M_1:
Zustände: q1, q2, q3
Startzustand: q1
Finalzustände: q3
Transitionen:
    q1, 0 -> q2
    q2, 1 -> q1
    q2, 0 -> q3
    q2, 1 -> q3
    q3, 1 -> q2
Q:=Q×{0,1,2}Q' := Q \times \{0, 1, 2\}
q0:=(q0,0)q_0' := (q_0, 0)
F:={(q,2)qF}F' := \{(q, 2) \mid q \in F\}

δ\delta':
For all qQq \in Q, i{0,1,2}i \in \{0, 1, 2\}:
- δ((q,i),1):={(p,i)pδ(q,1)}\delta'((q, i), 1) := \{(p, i) \mid p \in \delta(q, 1)\}
- δ((q,i),0):={(p,i)pδ(q,0)}\delta'((q, i), 0) := \{(p, i) \mid p \in \delta(q, 0)\}
- δ((q,i),ϵ):={{(p,i+1)pδ(q,0)}if i{0,1}if i=2\delta'((q, i), \epsilon) := \begin{cases}
  \{(p, i+1) \mid p \in \delta(q, 0)\} & \text{if } i \in \{0, 1\} \\
  \emptyset & \text{if } i = 2
  \end{cases}

Konstruktionsidee (optional):
The construction creates three "layers" of the original NFA, where each layer tracks how many zeros have been removed so far. The second component i{0,1,2}i \in \{0, 1, 2\} counts the number of zeros removed. On reading a 0, we can either follow the original transition (keeping the count) or skip it via an ε-transition (incrementing the count). On reading a 1, we simply follow the original transition. We accept only when we reach a final state of M after removing exactly 2 zeros.

Ihr Konstruktionsergebnis für M1M_1:
States: (q1,0),(q1,1),(q1,2),(q2,0),(q2,1),(q2,2),(q3,0),(q3,1),(q3,2)(q_1,0), (q_1,1), (q_1,2), (q_2,0), (q_2,1), (q_2,2), (q_3,0), (q_3,1), (q_3,2)
Start state: (q1,0)(q_1,0)
Final state: (q3,2)(q_3,2)

Transitions:
From (q1,0)(q_1,0): 0(q2,0)0 \to (q_2,0), ϵ(q2,1)\epsilon \to (q_2,1)
From (q1,1)(q_1,1): 0(q2,1)0 \to (q_2,1), ϵ(q2,2)\epsilon \to (q_2,2)
From (q1,2)(q_1,2): 0(q2,2)0 \to (q_2,2)

From (q2,0)(q_2,0): 1{(q1,0),(q3,0)}1 \to \{(q_1,0), (q_3,0)\}, 0(q3,0)0 \to (q_3,0), ϵ(q3,1)\epsilon \to (q_3,1)
From (q2,1)(q_2,1): 1{(q1,1),(q3,1)}1 \to \{(q_1,1), (q_3,1)\}, 0(q3,1)0 \to (q_3,1), ϵ(q3,2)\epsilon \to (q_3,2)
From (q2,2)(q_2,2): 1{(q1,2),(q3,2)}1 \to \{(q_1,2), (q_3,2)\}, 0(q3,2)0 \to (q_3,2)

From (q3,0)(q_3,0): 1(q2,0)1 \to (q_2,0)
From (q3,1)(q_3,1): 1(q2,1)1 \to (q_2,1)
From (q3,2)(q_3,2): 1(q2,2)1 \to (q_2,2)

Subproblem c (3.0/3.0P)

Es gilt weiterhin Σ={0,1}\Sigma=\{0,1\}. Für eine Sprache LΣL\subseteq\Sigma^* bezeichnet L0L^{\uparrow 0} die Sprache, die man erhält, wenn man den Wörtern aus LL jeweils zwei Nullen hinzufügt. Formal gilt
L0:={u0v0wuvwLu,v,wΣ}L^{\uparrow 0}:= \{u0v0w \mid uvw\in L \wedge u,v,w\in\Sigma^*\}.
Zeigen oder widerlegen Sie: Für jede nichtleere Sprache LΣL\subseteq \Sigma^* gilt L0LL^{\uparrow 0}\neq L.
Falls Sie die Aussage mit einem Gegenbeispiel widerlegen möchten, zeigen Sie auch die Korrektheit des Gegenbeispiels.
WahrFalsch
Proof that the statement is true:

For any non-empty language LΣL \subseteq \Sigma^*, I will show that L0LL^{\uparrow 0} \neq L.

Since LL is non-empty, there exists at least one word in LL. Let wLw \in L be a word with the minimum number of zeros among all words in LL. Let's say ww contains exactly kk zeros.

Key observation: Every word in L0L^{\uparrow 0} is formed by adding exactly 2 zeros to some word from LL. Since every word in LL has at least kk zeros, every word in L0L^{\uparrow 0} has at least k+2k + 2 zeros.

Now I consider two cases:

Case 1: k<2k < 2 (i.e., ww has 0 or 1 zeros)
- Then wLw \in L has fewer than 2 zeros
- But every word in L0L^{\uparrow 0} has at least k+22k + 2 \geq 2 zeros
- Therefore wLw \in L but wL0w \notin L^{\uparrow 0}
- Hence L⊈L0L \not\subseteq L^{\uparrow 0}, so LL0L \neq L^{\uparrow 0}

Case 2: k2k \geq 2 (i.e., all words in LL have at least 2 zeros)
- For ww to be in L0L^{\uparrow 0}, we would need w=u0v0zw = u0v0z for some uvzLuvz \in L
- But then uvzuvz would have exactly k2k - 2 zeros
- This contradicts our assumption that kk is the minimum number of zeros in any word in LL
- Therefore wLw \in L but wL0w \notin L^{\uparrow 0}
- Hence L⊈L0L \not\subseteq L^{\uparrow 0}, so LL0L \neq L^{\uparrow 0}

In both cases, we have LL0L \neq L^{\uparrow 0}. Therefore, the statement is true.

Exercise 4: NFA zu regulärem Ausdruck


Subproblem a (9.0/9.0P)

Wir betrachten den rechts abgebildeten NFA NN über dem Alphabet {a,b}\{a,b\}. Berechnen Sie mit dem graphischen Algorithmus aus der Vorlesung (nicht mit Ardens Lemma) einen regulären Ausdruck rr, sodass L(r)=L(N)L(r) = L(N). Geben Sie dabei nach jeder Anwendung einer Transformationsregel den Automaten graphisch an und vereinfachen Sie die regulären Ausdrücke in den Zwischenschritten nicht. (Ausnahme: Sie dürfen die Vereinfachung εααεα\varepsilon \alpha \equiv \alpha \varepsilon \equiv \alpha anwenden.) Entfernen Sie die Zustände in aufsteigender Reihenfolge (bezüglich ihrer Zustandsnummer).
NFA N:
Zustände: 1, 2, 3
Startzustand: 1
Finalzustände: 3
Transitionen:
    1, a -> 2
    1, b -> 3
    2, a -> 1
    3, a -> 3
    3, b -> 2
Zwischenschritte:

**Ausgangs-NFA mit hinzugefügtem Endzustand $q_f$:**
```
Zustände: 1 (Start), 2, 3, q_f (Final)
Transitionen:
1 --a--> 2
1 --b--> 3  
2 --a--> 1
3 --a--> 3
3 --b--> 2
3 --ε--> q_f
```

**Nach Entfernung von Zustand 2:**
Für jeden Pfad durch Zustand 2 füge ich eine neue Kante hinzu:
- Von 1 nach 1: $1 \xrightarrow{a} 2 \xrightarrow{a} 1$ ergibt Kante mit Label $aa$
- Von 3 nach 1: $3 \xrightarrow{b} 2 \xrightarrow{a} 1$ ergibt Kante mit Label $ba$
- Von 1 nach 3: bleibt $b$ (kein Pfad über 2)
- Von 3 nach 3: bleibt $a$ (kein Pfad über 2)

```
Zustände: 1 (Start), 3, q_f (Final)
Transitionen:
1 --aa--> 1
1 --b--> 3
3 --a--> 3
3 --ba--> 1
3 --ε--> q_f
```

**Nach Entfernung von Zustand 3:**
Zustand 3 hat eine Selbstschleife mit Label $a$, also ist der Kleene-Stern $a^*$.
Für jeden Pfad durch Zustand 3:
- Von 1 nach 1: bestehende Kante $aa$ plus $1 \xrightarrow{b} 3 \xrightarrow{a^*} 3 \xrightarrow{ba} 1$ ergibt $aa + ba^*ba$
- Von 1 nach $q_f$: $1 \xrightarrow{b} 3 \xrightarrow{a^*} 3 \xrightarrow{\varepsilon} q_f$ ergibt $ba^*$

```
Zustände: 1 (Start), q_f (Final)
Transitionen:
1 --(aa + ba*ba)--> 1
1 --ba*--> q_f
```

**Finaler Automat:**
Zustand 1 hat eine Selbstschleife mit Label $(aa + ba^*ba)$, also ist der Kleene-Stern $(aa + ba^*ba)^*$.
Der Pfad von 1 nach $q_f$ ist: $(aa + ba^*ba)^* \cdot ba^*$

Regulärer Ausdruck: $r = (aa + ba^*ba)^*ba^*$

Subproblem b (3.0/3.0P)

Geben Sie eine rechtslineare Grammatik für L(N)L(N) mit höchstens 3 Nichtterminalen an.

Hinweis: In rechtslinearen Grammatiken sind keine ε\varepsilon-Produktionen außer SεS \to \varepsilon erlaubt.
S -> aA | bB | b
A -> aS
B -> aB | bA | a

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (4.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S → A | B
A → aAb | C
C → aC | ε
B → aB | D
D → bDa | ε

Grammatik für L2L_2:
S → aT
T → aTX | X
X → a | b | aX | bX

Grammatik für L3L_3:
S → XBY
X → aXb | ε
B → bB | b
Y → bYa | ε
0: wrong language: does not generate abaa

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
Regulärer Ausdruck: a(ab)+a(a|b)^+

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
Wort, falls LiLϵ(M)L_i\neq L_\epsilon(M), sonst „-“.
L1L_1: aaaa
L2L_2: aaaa
L3L_3: -

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)

Welche der folgenden Sprachen sind entscheidbar?
{wΣ:φw ist total}\{w\in\Sigma^* :\varphi_w \text{ ist total}\}{wΣ:φw(0)=0}\{w\in\Sigma^* :\varphi_w(0) = 0\}{wΣ:φw ist berechenbar}\{w \in \Sigma^* :\varphi_w \text{ ist berechenbar}\}

Subproblem b (2.0/2.0P)

Sei LL eine beliebige unentscheidbare Sprache und aΣa\in\Sigma. Welche der folgenden Aussagen sind wahr?

Hinweis: LaL^a ist die Residualsprache bezüglich aa von LL.
L\overline L ist unentscheidbarLaL^a ist unentscheidbarEs gibt keine TM MM mit L(M)=LL(M) = L

Subproblem c (2.0/2.0P)

Sei MM eine beliebige deterministische Turingmaschine, sodass es eine Eingabe wΣw \in \Sigma^* gibt, auf der MM unendlich viele Schritte macht. Welche Aussagen sind wahr?
wL(M)w \notin L(M)L(M)L(M) ist unentscheidbarL(M)L(M) ist semi-entscheidbar

Subproblem d (2.0/2.0P)

Welche Aussagen sind wahr?
Jede reguläre Sprache ist in NP\text{NP}.Jede kontextfreie Sprache ist in P\text{P}.Sei LPL \in \text{P}. Dann gilt LNP\overline L \in \text{NP}.

Subproblem e (2.0/2.0P)

Angenommen, PNP\text{P} \neq \text{NP}. Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass ANPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?
ABA \subseteq BBAB \subseteq AApBA \leq_p BBpAB \leq_p A

Subproblem f (4.0/4.0P)

Seien A,BΣA,B\subseteq\Sigma^* beliebige Sprachen, sodass AA unentscheidbar ist. Zeigen oder widerlegen Sie: Mindestens eine der Sprachen ABA \cup B und ABA \cup \overline B ist unentscheidbar.
WahrFalsch
Beweis:

Wir zeigen die Aussage durch Widerspruch.

Annahme: Beide Sprachen ABA \cup B und ABA \cup \overline{B} sind entscheidbar.

Wenn beide Sprachen entscheidbar sind, dann ist auch ihr Schnitt entscheidbar (der Schnitt entscheidbarer Sprachen ist entscheidbar).

Betrachten wir den Schnitt:
(AB)(AB)(A \cup B) \cap (A \cup \overline{B})

Nach den Distributivgesetzen der Mengenlehre gilt:
(AB)(AB)=A(BB)=A=A(A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) = A \cup \emptyset = A

Das bedeutet: Wenn sowohl ABA \cup B als auch ABA \cup \overline{B} entscheidbar wären, dann wäre auch AA entscheidbar.

Dies ist ein Widerspruch zur Voraussetzung, dass AA unentscheidbar ist.

Daher muss mindestens eine der beiden Sprachen ABA \cup B oder ABA \cup \overline{B} unentscheidbar sein.

Die Aussage ist somit wahr.

Exercise 7: Reduktion

Zeigen Sie für jedes der folgenden Probleme AA entweder, dass es in P\mathsf{P} liegt, oder, dass es NP\mathsf{NP}-hart ist.
Geben Sie hierfür jeweils eine geeignete polynomielle Reduktion an und begründen Sie deren Korrektheit.

Reduktionsfunktionen müssen präzise definiert sein und Sie müssen klar angeben, welche Probleme Sie reduzieren. Die Korrektheit der Reduktion müssen Sie aber nur skizzieren und nicht formal beweisen.

Achtung: Auch um zu zeigen, dass das Problem in P\mathsf{P} liegt, ist eine Reduktion anzugeben!

Hinweis: Um zu zeigen, dass ein Problem AA in P\mathsf{P} liegt, geben Sie eine Reduktion ApBA\le_p B für ein BPB\in\mathsf{P} an, reduzieren Sie also AA auf ein Problem BB, von dem wir wissen, dass es in P\mathsf{P} liegt, z.B. 2COL\mathsf{2COL} oder 2KNF-SAT\mathsf{2KNF\text{-}SAT}.

Um zu zeigen, dass ein Problem AA NP\mathsf{NP}-hart ist, geben Sie eine Reduktion BpAB\le_p A an, wobei BB ein bekanntes NP-hartes Problem ist, etwa 3COL\mathsf{3COL}, SAT\mathsf{SAT}, oder CLIQUE\mathsf{CLIQUE}.

Subproblem a (6.0/6.0P)

Gegeben: Drei KNF-Formeln F1,F2,F3F_1, F_2, F_3 mit Variablen aus VV.

Problem AA: Gibt es eine Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\}, die genau zwei der drei Formeln erfüllt?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: SATpA\mathsf{SAT} \le_p A
Begründung:
Gegeben eine CNF-Formel FF mit Variablen aus VV, konstruiere ich drei CNF-Formeln wie folgt:
- F1=FF_1 = F
- F2=(z)F_2 = (z) wobei zz eine neue Variable ist (nicht in VV)
- F3=(¬z)F_3 = (\neg z)

Diese Reduktion ist polynomiell, da wir nur zwei triviale einelementige Klauseln hinzufügen.

Korrektheit:
- Falls FF erfüllbar ist: Sei σ\sigma eine erfüllende Belegung für FF. Erweitere σ\sigma um z=1z=1. Dann erfüllt diese Belegung F1F_1 (da FF erfüllt ist) und F2F_2 (da z=1z=1), aber nicht F3F_3 (da ¬z=0\neg z = 0). Also werden genau 2 Formeln erfüllt.

- Falls FF nicht erfüllbar ist: Für jede Belegung ist F1F_1 falsch. Da F2F_2 und F3F_3 sich gegenseitig ausschließen (eine fordert z=1z=1, die andere z=0z=0), kann höchstens eine von beiden erfüllt werden. Also wird insgesamt höchstens 1 Formel erfüllt, niemals genau 2.

Daher gilt: FF ist erfüllbar \Leftrightarrow es existiert eine Belegung, die genau zwei der drei Formeln F1,F2,F3F_1, F_2, F_3 erfüllt.

Subproblem b (8.0/8.0P)

Gegeben: Eine 2KNF-Formel FF mit Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\}, eine Menge {1,...,l}\{1, ..., l\} von Farben (mit l>0l>0) und eine Funktion g:V{1,...,l}g: V \to \{1 ,...,l\}, die jeder Variable eine Farbe zuordnet.

Problem AA: Gibt es eine erfüllende Belegung σ\sigma, sodass alle Variablen, die von σ\sigma zu Wahr gesetzt werden, unterschiedliche Farben haben? Formal: gibt es eine erfüllende Belegung σ:V{0,1}\sigma:V\rightarrow\{0,1\} mit g(xi)g(xj)g(x_i) \neq g(x_j) für alle i<jni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?
APA\in\mathsf{P}AA ist NP\mathsf{NP}-hart
Reduktion: Ap2SATA \le_p \mathsf{2SAT}
Begründung:
Gegeben eine Instanz (F,g)(F, g) von Problem AA, konstruiere ich eine 2KNF-Formel FF' wie folgt:

1. Beginne mit allen Klauseln aus FF
2. Für jedes Paar von Variablen xi,xjx_i, x_j mit i<ji < j und g(xi)=g(xj)g(x_i) = g(x_j) (gleiche Farbe), füge die Klausel (¬xi¬xj)(\neg x_i \vee \neg x_j) zu FF' hinzu

Polynomialität: Die Konstruktion ist polynomiell, da:
- Wir höchstens (n2)=O(n2)\binom{n}{2} = O(n^2) neue Klauseln hinzufügen
- Jede neue Klausel hat genau 2 Literale
- FF' bleibt eine 2KNF-Formel

Korrektheit:
- Falls (F,g)(F, g) eine Lösung hat: Sei σ\sigma eine erfüllende Belegung für FF, bei der alle wahren Variablen unterschiedliche Farben haben. Dann erfüllt σ\sigma auch FF', da:
  - Alle ursprünglichen Klauseln aus FF sind erfüllt
  - Für jede hinzugefügte Klausel (¬xi¬xj)(\neg x_i \vee \neg x_j) mit g(xi)=g(xj)g(x_i) = g(x_j) gilt: höchstens eine der Variablen ist wahr (da sie gleiche Farbe haben), also ist die Klausel erfüllt

- Falls FF' erfüllbar ist: Jede erfüllende Belegung σ\sigma für FF' erfüllt auch FF (da FFF \subseteq F') und respektiert die Farbenbedingung, da die Klauseln (¬xi¬xj)(\neg x_i \vee \neg x_j) verhindern, dass zwei Variablen gleicher Farbe beide wahr sind

Da 2SAT in P liegt, liegt auch Problem AA in P.

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)(L_i)^* nicht regulär ist.
L1:={(ab)n:nN}L_1 := \{(ab)^n:n\in\mathbb{N}\}L2:={anbn:nN}L_2 := \{a^nb^n:n\in\mathbb{N}\}L3:={anbm:n,mNnm}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\}
Begründung für i=2i=2:
(L2)(L_2)^* ist nicht regulär. Dies kann mit dem Pumping-Lemma gezeigt werden: Angenommen (L2)(L_2)^* wäre regulär mit Pumping-Länge pp. Betrachte w=apbpapbp(L2)w = a^pb^pa^pb^p \in (L_2)^* (Konkatenation zweier Strings aus L2L_2). Nach dem Pumping-Lemma gibt es eine Zerlegung w=xyzw = xyz mit xyp|xy| \leq p und y>0|y| > 0. Da xyp|xy| \leq p, besteht yy nur aus aa's des ersten Blocks, also y=aky = a^k für k>0k > 0. Dann ist xy0z=apkbpapbpxy^0z = a^{p-k}b^pa^pb^p. Dieser String kann nicht als Konkatenation von Strings aus L2L_2 dargestellt werden, da die erste Gruppe weniger aa's als bb's hat und die verbleibenden bb's nicht mit den folgenden aa's zu einem balancierten String kombiniert werden können. Widerspruch!

Subproblem b (0.0/1.0P)

Gibt es eine kontextfreie Grammatik GG in Chomsky-Normalform mit höchstens 66 Produktionen und L(G)={a12,a9}L(G)=\{a^{12},a^9\}? Falls ja, geben Sie eine solche Grammatik an, falls nein, begründen Sie dies kurz.
Ja, Grammatik:Nein, Begründung:
wrong answer for choice (0)
In CNF benötigt man für einen String der Länge nn genau n1n-1 Anwendungen binärer Regeln. Für a9a^9 brauchen wir 8 binäre Regelanwendungen, für a12a^{12} brauchen wir 11. Die Ableitungsbäume müssen sich strukturell unterscheiden, um diese verschiedenen Längen zu erreichen. Mit nur 6 Produktionen können wir nicht genügend verschiedene Ableitungspfade konstruieren, um genau diese beiden spezifischen Längen zu erzeugen, da wir mehrere Nicht-Terminale mit ihren jeweiligen Produktionen benötigen würden.
0: could not parse value In CNF benötigt man für einen String der Länge n genau n-1 Anwendungen binärer Regeln. Für a^9 brauchen wir 8 binäre Regelanwendungen, für a^{12} brauchen wir 11. Die Ableitungsbäume müssen sich strukturell unterscheiden, um diese verschiedenen Längen zu erreichen. Mit nur 6 Produktionen können wir nicht genügend verschiedene Ableitungspfade konstruieren, um genau diese beiden spezifischen Längen zu erzeugen, da wir mehrere Nicht-Terminale mit ihren jeweiligen Produktionen benötigen würden. for type cfg

Subproblem c (2.0/2.0P)

Sei L{0,1}L\subseteq\{0,1\}^* eine beliebige kontextfreie und nicht reguläre Sprache. Welche der folgenden Aussagen sind wahr? (Es können mehrere sein.) Wählen Sie eine solche Aussage und begründen Sie kurz, wieso diese Aussage wahr ist.
Es gibt eine unentscheidbare Sprache LLL'\subseteq L.Jede Sprache LLL'\subseteq L ist entscheidbar.
Begründung für Aussage 1:
Da LL kontextfrei aber nicht regulär ist, muss LL unendlich sein (jede endliche Sprache ist regulär). Eine unendliche Menge hat überabzählbar viele Teilmengen. Es gibt aber nur abzählbar viele entscheidbare Sprachen, da es nur abzählbar viele Turingmaschinen gibt. Nach dem Schubfachprinzip muss es daher überabzählbar viele unentscheidbare Teilmengen von LL geben. Insbesondere existiert mindestens eine unentscheidbare Sprache LLL' \subseteq L.