Exam 2024_endterm.txt — z-ai/glm-4.5

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 0.0/2.0 1.0/3.0 0.0/3.0 9.0/16.0
2: Residualsprachen und Minimierung 4.0/5.0 2.0/2.0 2.0/2.0 2.0/2.0 1.0/3.0 4.0/4.0 15.0/18.0
3: NFA-Konstruktion 2.0/3.0 7.0/7.0 0.0/3.0 9.0/13.0
4: NFA zu regulärem Ausdruck 3.0/9.0 0.0/3.0 3.0/12.0
5: Kontextfreie Sprachen 2.0/6.0 4.0/4.0 3.0/3.0 9.0/13.0
6: Quiz: Berechenbarkeit und Komplexität 2.0/2.0 0.0/2.0 2.0/2.0 2.0/2.0 2.0/2.0 4.0/4.0 12.0/14.0
7: Reduktion 6.0/6.0 8.0/8.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 74.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 (0.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
wrong answer for choice (2)

Subproblem f (1.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=(aa+ab+ba+bb)r_1=(aa+ab+ba+bb)^*
r2=b(ab)r_2=b^*(ab)^*
r3=(bb+ab)r_3=(bb+ab)^*
1: wrong language: does not contain abb
2: wrong language: does not contain babb

Subproblem g (0.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
wrong answer for choice (0)
According to the Myhill-Nerode theorem, the set of residual languages of a language L uniquely determines L. If two DFAs have the same set of residual languages, they must recognize the same language. Therefore, there cannot exist a DFA M' such that L(M) and L(M') have the same residual languages but L(M) ≠ L(M').

Exercise 2: Residualsprachen und Minimierung


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

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:
Ein Zustand qq gehört zu SS, wenn er nur zu sich selbst äquivalent ist. Das bedeutet, dass für alle anderen Zustände pqp \neq q der Eintrag (q,p)(q,p) in der Äquivalenztabelle nicht "==" ist. 

In der Tabelle sehen wir:
- Zustand 2 ist nicht äquivalent zu 0, 1, 3, 4 und 5.
- Zustand 5 ist nicht äquivalent zu 0, 1, 2, 3 und 4.

Alle anderen Zustände sind zu mindestens einem anderen Zustand äquivalent:
- 0 ist äquivalent zu 1
- 1 ist äquivalent zu 0
- 3 ist äquivalent zu 4
- 4 ist äquivalent zu 3

Daher sind nur die Zustände 2 und 5 nur zu sich selbst äquivalent.

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 (1.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={bc}L^{cba^n}=\{bc\}
Lan={can}L^{a^n}=\{ca^n\}

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:
Ohne Einschränkung gelte i<ji < j. Wir zeigen, dass biLajb^i \in L^{a^j} aber biLaib^i \notin L^{a^i}.

1. biLajb^i \in L^{a^j}:
   ajbiLa^jb^i \in L da jij \ne i (da i<ji < j). Nach Definition der Residualsprache gilt damit biLajb^i \in L^{a^j}.

2. biLaib^i \notin L^{a^i}:
   aibiLa^ib^i \notin L da i=ii = i. Nach Definition der Residualsprache gilt damit biLaib^i \notin L^{a^i}.

Da bib^i in der einen aber nicht in der anderen Residualsprache liegt, gilt LaiLajL^{a^i} \ne L^{a^j}.

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 (2.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=(10)(10)1(01)(01)1s_3=(10)^*\mid(10)^*1(01)^*\mid(01)^*1
2: wrong language: contains 1

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(i):qQ,i{0,1,2}}Q'=\{q^{(i)} : q \in Q, i \in \{0, 1, 2\}\}
q0=q0(0)q_0'=q_0^{(0)}
F={q(2):qF}F'=\{q^{(2)} : q \in F\}

δ\delta':
For each qQq \in Q and i{0,1}i \in \{0, 1\}:
- For each xΣx \in \Sigma, δ(q(i),x)={p(i):pδ(q,x)}\delta'(q^{(i)}, x) = \{p^{(i)} : p \in \delta(q, x)\}.
- δ(q(i),ϵ)={p(i):pδ(q,ϵ)}{p(i+1):pδ(q,0)}\delta'(q^{(i)}, \epsilon) = \{p^{(i)} : p \in \delta(q, \epsilon)\} \cup \{p^{(i+1)} : p \in \delta(q, 0)\}.

For each qQq \in Q:
- For each xΣ{ϵ}x \in \Sigma \cup \{\epsilon\}, δ(q(2),x)={p(2):pδ(q,x)}\delta'(q^{(2)}, x) = \{p^{(2)} : p \in \delta(q, x)\}.

Konstruktionsidee (optional):
Die Idee hinter der Konstruktion ist, dass der ϵ\epsilon-NFA MM' den NFA MM simuliert, aber genau zwei Nullen überspringen muss. Die Zustände von MM' haben die Form q(i)q^{(i)}, wobei qq ein Zustand von MM ist und i{0,1,2}i \in \{0, 1, 2\} angibt, wie viele Nullen bereits übersprungen wurden. 

Wenn MM' in einem Zustand q(i)q^{(i)} mit i<2i < 2 ist, kann er entweder ein Symbol normal verarbeiten (gemäß den Transitionen von MM) oder eine Null überspringen (mittels einer ϵ\epsilon-Transition, die den Zustand zu q(i+1)q^{(i+1)} übergehen lässt, wobei alle möglichen Zustände berücksichtigt werden, die MM beim Lesen einer Null erreichen würde).

Wenn MM' in einem Zustand q(2)q^{(2)} ist, hat er bereits zwei Nullen übersprungen und verarbeitet die restlichen Symbole normal gemäß den Transitionen von MM.

Ein Wort ww wird von MM' akzeptiert, wenn MM das Wort u0v0wu0v0w für einige u,vΣu, v \in \Sigma^* akzeptieren würde, was genau der Definition von L0L^{\downarrow 0} entspricht.

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

Transitionen:
q1^(0) --0--> q2^(0)
q1^(0) --ε--> q2^(1)
q2^(0) --1--> q1^(0), q3^(0)
q2^(0) --0--> q3^(0)
q2^(0) --ε--> q3^(1)
q3^(0) --1--> q2^(0)

q1^(1) --0--> q2^(1)
q1^(1) --ε--> q2^(2)
q2^(1) --1--> q1^(1), q3^(1)
q2^(1) --0--> q3^(1)
q2^(1) --ε--> q3^(2)
q3^(1) --1--> q2^(1)

q1^(2) --0--> q2^(2)
q2^(2) --1--> q1^(2), q3^(2)
q2^(2) --0--> q3^(2)
q3^(2) --1--> q2^(2)

Subproblem c (0.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
wrong answer for choice (0)
The statement is false. A counterexample is L={0,1}{00}{0,1}L = \{0,1\}^* \cdot \{00\} \cdot \{0,1\}^*, the language of all strings that contain "00" as a substring.

To show that L0=LL^{\uparrow 0} = L:

1. LL0L \subseteq L^{\uparrow 0}: For any word wLw \in L, we can write w=u00vw = u00v for some u,vΣu, v \in \Sigma^*. Then w=u00v=u0ε0vL0w = u00v = u0\varepsilon 0v \in L^{\uparrow 0} (taking u=uu' = u, v=εv' = \varepsilon, w=vw' = v).

2. L0LL^{\uparrow 0} \subseteq L: For any word wL0w \in L^{\uparrow 0}, we have w=u0v0ww = u0v0w' for some u,v,wΣu, v, w' \in \Sigma^* such that uvwLuvw' \in L. Since uvwLuvw' \in L, we have uvw=x00yuvw' = x00y for some x,yΣx, y \in \Sigma^*. Then w=u0v0w=u0v0x00yw = u0v0w' = u0v0x00y, which contains "00" as a substring. So wLw \in L.

Since LL is non-empty (for example, 00L00 \in L) and L0=LL^{\uparrow 0} = L, this is a valid counterexample to the statement.

Exercise 4: NFA zu regulärem Ausdruck


Subproblem a (3.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:
1. Add a new start state (S) and a new final state (F)
   - Add ε-transition from S to 1
   - Add ε-transition from 3 to F

   States: S, 1, 2, 3, F
   Start state: S
   Final state: F
   Transitions:
   - S, ε -> 1
   - 1, a -> 2
   - 1, b -> 3
   - 2, a -> 1
   - 3, a -> 3
   - 3, b -> 2
   - 3, ε -> F

2. Remove state 1
   - Add transition S, a -> 2
   - Add transition S, b -> 3
   - Add transition 2, aa -> 2
   - Add transition 2, ab -> 3

   States: S, 2, 3, F
   Start state: S
   Final state: F
   Transitions:
   - S, a -> 2
   - S, b -> 3
   - 2, aa -> 2
   - 2, ab -> 3
   - 3, a -> 3
   - 3, b -> 2
   - 3, ε -> F

3. Remove state 2
   - Add transition S, a(aa)* -> 3
   - Add transition S, aab -> 3
   - Add transition 3, b(aa)* -> 3
   - Add transition 3, bab -> 3

   States: S, 3, F
   Start state: S
   Final state: F
   Transitions:
   - S, b -> 3
   - S, a(aa)* -> 3
   - S, aab -> 3
   - 3, a -> 3
   - 3, b(aa)* -> 3
   - 3, bab -> 3
   - 3, ε -> F

4. Remove state 3
   - Add transition S, (b + a(aa)* + aab) * (a + b(aa)* + bab)* * ε -> F

   States: S, F
   Start state: S
   Final state: F
   Transitions:
   - S, (b + a(aa)* + aab) * (a + b(aa)* + bab)* * ε -> F

Regulärer Ausdruck: $r = (b + a(aa)* + aab)  (a + b(aa)* + bab)*$
wrong on word a

Subproblem b (0.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
A -> aS
B -> aB | bA | ε
invalid production B -> ε

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 (2.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 → TA | AT
T → aTb | bTa | ε
A → aA | ε

Grammatik für L2L_2:
S → aSB | aT
B → aB | bB | a | b
T → aT | bT | a | b

Grammatik für L3L_3:
S → aSb | T
T → bT | bU
U → bU | bV
V → bVa | b
0: wrong language: generates baa
2: wrong language: does not generate 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_1L2L_2L3L_3
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)
L1L_1: ab
L2L_2: aa
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 (0.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
wrong answer for choice (1)

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
Die Aussage ist wahr. Wir beweisen dies durch Widerspruch.

Angenommen, beide Sprachen ABA \cup B und ABA \cup \overline{B} sind entscheidbar. Dann können wir einen Entscheider für AA konstruieren:

Für eine Eingabe wΣw \in \Sigma^*:
1. Prüfe, ob wABw \in A \cup B (entscheidbar nach Annahme)
2. Prüfe, ob wABw \in A \cup \overline{B} (entscheidbar nach Annahme)

Fallunterscheidung:
- Wenn wAw \in A, dann gilt wABw \in A \cup B und wABw \in A \cup \overline{B}.
- Wenn wAw \notin A, dann gilt wABw \in A \cup B genau dann, wenn wBw \in B, und wABw \in A \cup \overline{B} genau dann, wenn wBw \in \overline{B}.

Da BB und B\overline{B} eine Partition von Σ\Sigma^* bilden, gilt für wAw \notin A:
- Wenn wBw \in B, dann wABw \in A \cup B aber wABw \notin A \cup \overline{B}.
- Wenn wBw \notin B, dann wABw \notin A \cup B aber wABw \in A \cup \overline{B}.

Daraus folgt:
- Wenn wABw \in A \cup B und wABw \in A \cup \overline{B}, dann wAw \in A.
- Wenn ww in genau einer der beiden Mengen liegt, dann wAw \notin A.

Dies ergibt einen Entscheidungsalgorithmus für AA, was im Widerspruch zur Voraussetzung steht, dass AA unentscheidbar ist.

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

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:
Given a CNF formula FF, we construct three CNF formulas F1,F2,F3F_1, F_2, F_3 as follows:
- F1=FF_1 = F
- F2=xF_2 = x (where xx is a new variable not in FF)
- F3=¬xF_3 = \neg x

If FF is satisfiable, let σ\sigma be a satisfying assignment for FF. Extend σ\sigma to σ\sigma' by setting σ(x)=0\sigma'(x) = 0. Then, σ\sigma' satisfies F1F_1 (since it satisfies FF) and F3F_3 (since it satisfies ¬x\neg x), but not F2F_2 (since it doesn't satisfy xx). So, σ\sigma' satisfies exactly two of the three formulas.

Conversely, if there exists an assignment σ\sigma that satisfies exactly two of the three formulas, then it must satisfy F1F_1 and either F2F_2 or F3F_3 (since it cannot satisfy both F2F_2 and F3F_3). In either case, it satisfies F1=FF_1 = F, so FF is satisfiable.

Therefore, FF is satisfiable if and only if there exists an assignment that satisfies exactly two of the three formulas F1,F2,F3F_1, F_2, F_3.

This reduction is polynomial-time, as we can construct F1,F2,F3F_1, F_2, F_3 from FF in polynomial time.

Therefore, AA is NP-hard.

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: Ap2KNF-SATA \le_p \mathsf{2KNF\text{-}SAT}
Begründung:
Given an instance of problem AA (a 2CNF formula FF, a set of colors {1,...,l}\{1, ..., l\}, and a coloring function g:V{1,...,l}g: V \to \{1, ..., l\}), we construct a new 2CNF formula FF' as follows:

1. Start with F=FF' = F.
2. For each color c{1,...,l}c \in \{1, ..., l\}, let Vc={xV:g(x)=c}V_c = \{x \in V : g(x) = c\} be the set of variables with color cc.
3. For each color cc and for each pair of distinct variables x,yVcx, y \in V_c, add the clause (¬x¬y)(\neg x \vee \neg y) to FF'.

The formula FF' is a 2CNF formula, and it can be constructed in polynomial time (since there are at most O(n2)O(n^2) additional clauses, where nn is the number of variables).

Now, FF' is satisfiable if and only if there exists a satisfying assignment for FF where at most one variable from each color class is set to true. This is exactly the condition required by problem AA.

Since 2CNF-SAT is in P, we can solve problem AA in polynomial time by reducing it to 2CNF-SAT and then solving the resulting 2CNF formula.

Therefore, APA \in \mathsf{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 (0.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\}
wrong answer for choice (2)
Begründung für i=2i=2:
Angenommen, (L2)(L_2)^* ist regulär. Dann existiert eine Pumping-Länge pp gemäß dem Pumping-Lemma für reguläre Sprachen.

Betrachte den String s=(ab)ps = (ab)^p. Dieser String ist in (L2)(L_2)^*, da er durch Konkatenation von pp Strings der Form abab aus L2L_2 gebildet werden kann.

Da s=2pp|s| = 2p \geq p, können wir das Pumping-Lemma anwenden. Sei s=xyzs = xyz mit xyp|xy| \leq p und y>0|y| > 0. Da xyp|xy| \leq p, muss yy ein Teilstring der ersten pp Symbole von ss sein, welche abwechselnd aa's und bb's sind.

Fall 1: yy besteht aus aa's, etwa y=aky = a^k für ein k>0k > 0. Dann hat xy2zxy^2z im ersten Segment kk mehr aa's als bb's. Dies bedeutet, dass der String nicht in Segmente der Form anibnia^{n_i}b^{n_i} zerlegt werden kann, also nicht in (L2)(L_2)^* liegt.

Fall 2: yy besteht aus bb's, etwa y=bky = b^k für ein k>0k > 0. Dann hat xy2zxy^2z im ersten Segment kk mehr bb's als aa's. Auch dies bedeutet, dass der String nicht in Segmente der Form anibnia^{n_i}b^{n_i} zerlegt werden kann, also nicht in (L2)(L_2)^* liegt.

In beiden Fällen erhalten wir einen Widerspruch zum Pumping-Lemma. Daher ist (L2)(L_2)^* nicht regulär.

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:
A1aA_1 \to a
A2A1A1A_2 \to A_1A_1
A4A2A2A_4 \to A_2A_2
A8A4A4A_8 \to A_4A_4
SA8A1S \to A_8A_1
SA8A4S \to A_8A_4

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 ist, ist LL entscheidbar. Zudem ist LL nicht regulär, weshalb LL unendlich sein muss (da alle endlichen Sprachen regulär sind). Jede unendliche entscheidbare Sprache enthält unentscheidbare Teilmengen. Dies folgt aus Kardinalitätsargumenten: Die Potenzmenge einer unendlichen Menge ist überabzählbar, während die Menge der entscheidbaren Sprachen abzählbar ist (da es nur abzählbar viele Turingmaschinen gibt). Daher muss es Sprachen LLL' \subseteq L geben, die nicht entscheidbar sind.