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

Exercise a b c d e f g Total
1: Quiz: Reguläre und kontextfreie Sprachen 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 3.0/3.0 3.0/3.0 16.0/16.0
2: Residualsprachen und Minimierung 5.0/5.0 2.0/2.0 2.0/2.0 2.0/2.0 3.0/3.0 4.0/4.0 18.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 6.0/6.0 4.0/4.0 3.0/3.0 13.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 1.0/1.0 2.0/2.0 5.0/5.0
Exam total 105.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 L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' 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?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{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...xk∈L∧x1,...,xk∈Σ∧k≥0}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}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(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:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,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\}.

r_1=((a+b)(a+b))^*
r_2=(ab + b)^*
r_3=((ab)^* b (ab)^* b (ab)^*)^* (ab)^*

Subproblem g (3.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', 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, DFA☐Falsch, Begründung 
Zustände: 0, 1, 2  
Startzustand: 2  
Finalzustände: 2  
Transitionen:  
    0, a -> 1  
    0, b -> 2  
    1, a -> 0  
    1, b -> 2  
    2, a -> 0  
    2, b -> 2

Exercise 2: Residualsprachen und Minimierung





Subproblem a (5.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): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon






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:={q∈Q:[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:
Die Menge SS besteht aus den Zuständen, für die in der Äquivalenztabelle kein Eintrag „==" mit einem anderen Zustand existiert. Das bedeutet, alle Paare, die diesen Zustand mit einem anderen Zustand betreffen, enthalten ein unterscheidendes Wort und nicht „==". Aus der Tabelle ergeben sich somit die Singleton-Äquivalenzklassen für die Zustände 2 und 5, da diese nur zu sich selbst äquivalent sind.






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 M′M':
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 M′M' 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,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.



Lanbnc={bnan}L^{a^nb^nc}=\{b^n a^n\}
Lcban=∅L^{cba^n}=\emptyset
Lan={y c yR an∣y∈{a,b}∗}L^{a^n}=\{y\, c\, y^R\, a^n \mid y \in \{a,b\}^*\}






Subproblem f (4.0/4.0P) 





Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\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 Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Sei o.B.d.A. i<ji<j. Betrachte das Wort v:=biv:=b^i. Es gilt v∈Lwj  ⟺  j≠iv\in L^{w_j}\iff j\neq i, was wahr ist, da j>ij>i. Jedoch gilt v∉Lwi  ⟺  i≠iv\notin L^{w_i}\iff i\neq i, was falsch ist. Also ist Lwi≠LwjL^{w_i}\ne L^{w_j}.








Exercise 3: NFA-Konstruktion


Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet L↓0L^{\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:
L↓0:={uvw:u0v0w∈L∧u,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:=(0∣1)(0∣1)r_1:=(0\mid 1)(0\mid 1), s1=ϵs_1=\epsilon
r2:=(0∣1)∗r_2:=(0\mid 1)^*, s2=(0∣1)∗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 Q′Q', q0′q_0', F′F', 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′,p′∈Q′,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)∣q∈F}F':=\{ (q,2) \mid q \in F \}

δ′\delta':
For all q∈Qq \in Q, k∈{0,1,2}k \in \{0,1,2\}, x∈Σx \in \Sigma:
δ′((q,k),x)={(p,k)∣p∈δ(q,x)}\delta'((q,k), x) = \{ (p, k) \mid p \in \delta(q, x) \}

For all q∈Qq \in Q, k∈{0,1}k \in \{0,1\}:
δ′((q,k),ϵ)={(p,k+1)∣p∈δ(q,0)}\delta'((q,k), \epsilon) = \{ (p, k+1) \mid p \in \delta(q, 0) \}

Konstruktionsidee (optional):
Die Konstruktion simuliert den NFA MM, wobei ϵ\epsilon-Transitionen verwendet werden, um genau zwei Nullen "einzufügen", ohne Eingabe zu konsumieren. Jede solche ϵ\epsilon-Transition simuliert eine Transition auf 0 im Original-NFA und erhöht den Zähler in der Zustandskomponente. Der Zähler stellt sicher, dass genau zwei Nullen eingefügt werden. Akzeptanz erfolgt nur in Zuständen (f,2)(f,2) mit f∈Ff \in F.

Ihr Konstruktionsergebnis für M1M_1:
Zustände: (q1,0)(q1,0), (q1,1)(q1,1), (q1,2)(q1,2), (q2,0)(q2,0), (q2,1)(q2,1), (q2,2)(q2,2), (q3,0)(q3,0), (q3,1)(q3,1), (q3,2)(q3,2)

Startzustand: (q1,0)(q1,0)

Finalzustände: (q3,2)(q3,2)

Transitionen auf 0:  
(q1,0)→(q2,0)(q1,0) \to (q2,0)  
(q1,1)→(q2,1)(q1,1) \to (q2,1)  
(q1,2)→(q2,2)(q1,2) \to (q2,2)  
(q2,0)→(q3,0)(q2,0) \to (q3,0)  
(q2,1)→(q3,1)(q2,1) \to (q3,1)  
(q2,2)→(q3,2)(q2,2) \to (q3,2)

Transitionen auf 1:  
(q2,0)→(q1,0)(q2,0) \to (q1,0), (q3,0)(q3,0)  
(q2,1)→(q1,1)(q2,1) \to (q1,1), (q3,1)(q3,1)  
(q2,2)→(q1,2)(q2,2) \to (q1,2), (q3,2)(q3,2)  
(q3,0)→(q2,0)(q3,0) \to (q2,0)  
(q3,1)→(q2,1)(q3,1) \to (q2,1)  
(q3,2)→(q2,2)(q3,2) \to (q2,2)

ϵ\epsilon-Transitionen:  
(q1,0)→(q2,1)(q1,0) \to (q2,1)  
(q1,1)→(q2,2)(q1,1) \to (q2,2)  
(q2,0)→(q3,1)(q2,0) \to (q3,1)  
(q2,1)→(q3,2)(q2,1) \to (q3,2)






Subproblem c (3.0/3.0P) 





Es gilt weiterhin Σ={0,1}\Sigma=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet L↑0L^{\uparrow 0} die Sprache, die man erhält, wenn man den Wörtern aus LL jeweils zwei Nullen hinzufügt. Formal gilt
L↑0:={u0v0w∣uvw∈L∧u,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 L↑0≠LL^{\uparrow 0}\neq L.
Falls Sie die Aussage mit einem Gegenbeispiel widerlegen möchten, zeigen Sie auch die Korrektheit des Gegenbeispiels.




☒Wahr☐Falsch



Angenommen, es gibt eine nichtleere Sprache L⊆{0,1}∗L \subseteq \{0,1\}^* mit L=L↑0L = L^{\uparrow 0}.  
Da LL nichtleer ist, gibt es eine minimale Wortlänge m≥0m \geq 0, sodass LL ein Wort der Länge mm enthält, aber keines kürzeren.  
Jedes Wort in L↑0L^{\uparrow 0} entsteht durch das Einfügen von genau zwei Nullen in ein Wort aus LL und hat daher Länge mindestens m+2m+2.  
Folglich enthält L↑0L^{\uparrow 0} keine Wörter der Länge m<m+2m < m+2, im Widerspruch dazu, dass L=L↑0L = L^{\uparrow 0} Wörter der Länge mm enthält.  
Daher kann keine solche nichtleere Sprache LL existieren, und die Aussage ist wahr.








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:

Zunächst erweitern wir den Automaten um einen neuen Startzustand q0q_0 und einen neuen Finalzustand qfq_f:

Zustände: q0q_0, 1, 2, 3, qfq_f

Startzustand: q0q_0

Finalzustände: qfq_f

Transitionen:

q0q_0, ε\varepsilon -> 1

1, a -> 2

1, b -> 3

2, a -> 1

3, a -> 3

3, b -> 2

3, ε\varepsilon -> qfq_f

Nach Entfernen von Zustand 1 (Schleife: keine, also ε\varepsilon im Stern):

Zustände: q0q_0, 2, 3, qfq_f

Startzustand: q0q_0

Finalzustände: qfq_f

Transitionen:

q0q_0, a -> 2

q0q_0, b -> 3

2, aa -> 2

2, ab -> 3

3, a -> 3

3, b -> 2

3, ε\varepsilon -> qfq_f

Nach Entfernen von Zustand 2 (Schleife: aa):

Zustände: q0q_0, 3, qfq_f

Startzustand: q0q_0

Finalzustände: qfq_f

Transitionen:

q0q_0, b∪a(aa)∗abb \cup a(aa)^{*}ab -> 3

3, a∪b(aa)∗aba \cup b(aa)^{*}ab -> 3

3, ε\varepsilon -> qfq_f

Nach Entfernen von Zustand 3 (Schleife: a∪b(aa)∗aba \cup b(aa)^{*}ab):

Zustände: q0q_0, qfq_f

Startzustand: q0q_0

Finalzustände: qfq_f

Transitionen:

q0q_0, (b∪a(aa)∗ab)(a∪b(aa)∗ab)∗(b \cup a(aa)^{*}ab)(a \cup b(aa)^{*}ab)^{*} -> qfq_f

Regulärer Ausdruck: r=(b∪a(aa)∗ab)(a∪b(aa)∗ab)∗r = (b \cup a(aa)^{*}ab)(a \cup b(aa)^{*}ab)^{*}






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=j∨j=k)∧i,j,k≥0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:w∈Σ∗∧∣w∣≥n∧n>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+k∧i,j,k≥0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}





Subproblem a (6.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 \to P W | W Q
P \to a P b | \varepsilon
Q \to b Q a | \varepsilon
W \to a W | \varepsilon

Grammatik für L2L_2:
S \to a M G
M \to a M G | T
T \to G T | \varepsilon
G \to a | b

Grammatik für L3L_3:
S \to P E Q
P \to a P b | \varepsilon
Q \to b Q a | \varepsilon
E \to b E | b






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_1☒L2L_2☐L3L_3



Regulärer Ausdruck: a(a∪b)+a(a\cup 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,X→p,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)☒L1≠Lϵ(M)L_1\neq L_\epsilon(M)☐L2=Lϵ(M)L_2=L_\epsilon(M)☒L2≠Lϵ(M)L_2\neq L_\epsilon(M)☒L3=Lϵ(M)L_3=L_\epsilon(M)☐L3≠Lϵ(M)L_3\neq L_\epsilon(M)



L1L_1: abab
L2L_2: abab
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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?




☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.







Subproblem e (2.0/2.0P) 





Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?




☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.




☒Wahr☐Falsch



Sei A⊆Σ∗A \subseteq \Sigma^* unentscheidbar und B⊆Σ∗B \subseteq \Sigma^* beliebig. Angenommen, sowohl C:=A∪BC := A \cup B als auch D:=A∪B‾D := A \cup \overline{B} sind entscheidbar. Dann ist auch C∩DC \cap D entscheidbar, da die entscheidbaren Sprachen unter Schnitt abgeschlossen sind. Es gilt jedoch
C∩D=(A∪B)∩(A∪B‾)=A∪(B∩B‾)=A∪∅=A.
C \cap D = (A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) = A \cup \emptyset = A.

Dies steht im Widerspruch zur Unentscheidbarkeit von AA. Also kann nicht CC und DD beide entscheidbar sein, d.h. mindestens eine der Sprachen A∪BA \cup B und A∪B‾A \cup \overline{B} ist unentscheidbar.








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 A≤pBA\le_p B für ein B∈PB\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 B≤pAB\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?




☐A∈PA\in\mathsf{P}☒AA ist NP\mathsf{NP}-hart



Reduktion: SAT≤pA\mathsf{SAT} \le_p A
Begründung:
Gegeben eine KNF-Formel FF über Variablen VV, führe eine frische Variable x∉Vx \notin V ein. Definiere F1=FF_1 = F, F2=(¬x)F_2 = (\neg x), F3=(x)F_3 = (x) über Variablen V∪{x}V \cup \{x\}.

Die Reduktion ist polynomialzeitig, da sie nur eine Variable hinzufügt und die Formeln kopiert bzw. einfach definiert.

Korrektheit: Eine Belegung σ\sigma erfüllt genau zwei der Formeln genau dann, wenn FF erfüllbar ist.

- Wenn FF erfüllbar ist durch σ0:V→{0,1}\sigma_0 : V \to \{0,1\}, dann erweitere zu σ\sigma mit σ(x)=0\sigma(x)=0: Erfüllt F1F_1 und F2F_2, nicht F3F_3 (genau zwei). Ähnlich für σ(x)=1\sigma(x)=1: Erfüllt F1F_1 und F3F_3, nicht F2F_2.
- Umgekehrt, wenn σ\sigma genau zwei erfüllt: Erfüllen von F2F_2 und F3F_3 erfordert x=0x=0 und x=1x=1, unmöglich. Also muss es F1F_1 und genau eine von F2F_2 oder F3F_3 erfüllen, d.h. σ\sigma eingeschränkt auf VV erfüllt FF. Somit ist FF erfüllbar.






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<j≤ni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?




☒A∈PA\in\mathsf{P}☐AA ist NP\mathsf{NP}-hart



Reduktion: A≤p2KNF-SATA \le_p \mathsf{2KNF\text{-}SAT}
Begründung:
Gegeben eine Instanz von AA: 2KNF-Formel FF über Variablen V={x1,…,xn}V=\{x_1,\dots,x_n\}, Farben {1,…,l}\{1,\dots,l\}, Funktion g:V→{1,…,l}g: V \to \{1,\dots,l\}.

Gruppiere die Variablen nach Farben: Für jede Farbe cc, sei Vc={x∈V∣g(x)=c}V_c = \{x \in V \mid g(x)=c\}.

Konstruiere eine neue 2KNF-Formel F′F' wie folgt: F′=F∧⋀c=1l⋀xi,xj∈Vc,i<j(¬xi∨¬xj)F' = F \land \bigwedge_{c=1}^l \bigwedge_{x_i,x_j \in V_c, i<j} (\neg x_i \lor \neg x_j).

Diese Konstruktion ist polynomialzeitig, da die Anzahl hinzugefügter Klauseln ∑c(∣Vc∣2)=O(n2)\sum_c \binom{|V_c|}{2} = O(n^2) beträgt und die Eingabegröße polynomiell darin beschränkt ist.

Korrektheit: F′F' ist erfüllbar genau dann, wenn es eine Belegung σ\sigma gibt, die FF erfüllt und für keine zwei Variablen mit gleicher Farbe beide auf 1 setzt, d.h. die wahren Variablen haben paarweise unterschiedliche Farben. Dies ist äquivalent zur Bedingung in AA.








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:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\}



Begründung für i=2i=2:
Angenommen (L2)∗(L_2)^* wäre regulär mit Pumplänge pp. Betrachte w=apbpapbp∈(L2)∗w = a^p b^p a^p b^p \in (L_2)^*. Dann liegt jede Zerlegung xyzxyz mit ∣xy∣≤p|xy| \le p, ∣y∣≥1|y| \ge 1 in den ersten apa^p. Für k=0k=0 ist xz=ap−tbpapbp∉(L2)∗xz = a^{p-t} b^p a^p b^p \notin (L_2)^*, da es nicht in aufeinanderfolgende Blöcke akbka^k b^k zerlegt werden kann (nach dem ersten möglichen Block ap−tbp−ta^{p-t} b^{p-t} bleibt btapbpb^t a^p b^p übrig, das mit bb beginnt, was kein Block kann). Widerspruch zum Pumplemma.






Subproblem b (1.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:



S -> C D | D D
D -> C C
C -> A B
B -> A A
A -> a






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 L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar.



Begründung für Aussage 1:
Da LL kontextfrei und nicht regulär ist, ist LL unendlich (denn endliche Sprachen sind regulär). Da LL entscheidbar ist, lässt sich eine effektive Aufzählung e1,e2,…e_1,e_2,\dots aller Wörter in LL berechnen. Sei K={n∈N∣K=\{n\in\mathbb{N}\mid die nn-te TM hält auf leerem Band}\}. Definiere L′={en∣n∈K}L'=\{e_n\mid n\in K\}. Dann ist L′⊆LL'\subseteq L unentscheidbar, da sich das Halteproblem auf L′L' reduzieren lässt.