Exam 2024_endterm.txt — deepseek/deepseek-r1-0528

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 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=(bab)r_2=(b|ab)*
r3=((ab)b(ab)b)(ab)r_3=((ab)*b(ab)*b)*(ab)*

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
Ja, es gibt einen solchen DFA MM'.  
MM' wird definiert durch:  
- Zustände: qε,qa,qbq_\varepsilon, q_a, q_b  
- Startzustand: qεq_\varepsilon  
- Finalzustände: qε,qbq_\varepsilon, q_b  
- Transitionen:  
  - δ(qε,a)=qa\delta(q_\varepsilon, a) = q_a  
  - δ(qε,b)=qb\delta(q_\varepsilon, b) = q_b  
  - δ(qa,a)=qa\delta(q_a, a) = q_a  
  - δ(qa,b)=qb\delta(q_a, b) = q_b  
  - δ(qb,a)=qa\delta(q_b, a) = q_a  
  - δ(qb,b)=qb\delta(q_b, b) = q_b  

Erklärung:  
- L(M)={w{a,b}w endet mit b}L(M) = \{w \in \{a,b\}^* \mid w \text{ endet mit } b\} (ohne ε\varepsilon).  
- L(M)={ε}{w{a,b}w endet mit b}L(M') = \{\varepsilon\} \cup \{w \in \{a,b\}^* \mid w \text{ endet mit } b\}.  
- Die Residualsprachen beider Sprachen sind identisch: {{xx endet mit b},{ε}{xx endet mit b}}\{ \{x \mid x \text{ endet mit } b\}, \{\varepsilon\} \cup \{x \mid x \text{ endet mit } b\} \}.  
- Aber L(M)L(M)L(M) \neq L(M'), da εL(M)\varepsilon \in L(M') aber εL(M)\varepsilon \notin L(M).

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:={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 genau dann, wenn er nicht äquivalent zu irgendeinem anderen Zustand pqp \neq q ist. In der Äquivalenztabelle aus Teil a) zeigt ein Gleichheitszeichen „==" an, dass zwei Zustände äquivalent sind. Für SS müssen wir daher Zustände identifizieren, bei denen kein Paar (q,p)(q,p) mit pqp \neq q als äquivalent markiert ist:
- Zustand 2: Alle Paare (2,p)(2,p) für p2p \neq 2 sind mit trennenden Wörtern markiert ((2,0):a(2,0):a, (2,1):a(2,1):a, (2,3):a(2,3):a, (2,4):a(2,4):a, (2,5):ε(2,5):\varepsilon), also ist 22 nur zu sich selbst äquivalent.
- Zustand 5: Alle Paare (5,p)(5,p) für p5p \neq 5 sind mit trennenden Wörtern markiert (implizit aus der Tabelle, z.B. (5,0):ε(5,0):\varepsilon via (0,5)(0,5), (5,2):ε(5,2):\varepsilon via (2,5)(2,5), etc.), also ist 55 nur zu sich selbst äquivalent.
- Andere Zustände (0,1,3,4) sind jeweils äquivalent zu mindestens einem anderen Zustand (0=10=1, 3=43=4) und gehören daher nicht zu SS.

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}\{0,1\}, \{2\}, \{3,4\}, \{5\}
Startzustand: {0,1}\{0,1\}
Finalzustände: {5}\{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^n a^n \}
Lcban=L^{cba^n}=\emptyset
Lan={vcvRanv{a,b}}L^{a^n}=\{ v c v^R a^n \mid v \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:
Seien i,jNi, j \in \mathbb{N} mit iji \neq j beliebig. Betrachte das Wort z=bjz = b^j.  
- zLwiz \in L^{w_i}, denn wiz=aibjLw_i z = a^i b^j \in L (da iji \neq j).  
- zLwjz \notin L^{w_j}, denn wjz=ajbjLw_j z = a^j b^j \notin L (da j=jj = j).  
Somit gilt LwiLwjL^{w_i} \neq L^{w_j}, da zz die Sprachen trennt.  
Da i,ji, j beliebig mit iji \neq j gewählt wurden, sind die Residualsprachen Lw0,Lw1,L^{w_0}, L^{w_1}, \dots paarweise verschieden.

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=\epsilon
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,k)q{q1,q2,q3},k{0,1,2}}Q':= Q \times \{0,1,2\} = \{ (q,k) \mid q \in \{q_1,q_2,q_3\}, k \in \{0,1,2\} \}
q0:=(q1,0)q_0':= (q_1,0)
F:={(q3,2)}F':= \{ (q_3,2) \}

δ\delta':
For all (q,k)Q(q,k) \in Q' and a{0,1}a \in \{0,1\}:
- If a=0a=0:
  δ((q,k),0)={(p,k)pδ(q,0)}{(q,k+1)k<2}
  \delta'((q,k),0) = \{ (p,k) \mid p \in \delta(q,0) \} \cup \{ (q,k+1) \mid k < 2 \}
  
- If a=1a=1:
  δ((q,k),1)={(p,k)pδ(q,1)}
  \delta'((q,k),1) = \{ (p,k) \mid p \in \delta(q,1) \}
  

Konstruktionsidee (optional):
MM' simuliert MM und verwaltet einen Zähler kk für entfernte Nullen. Bei einer 00 kann sie diese entweder normal verarbeiten (Zustandswechsel gemäß MM) oder entfernen (kk erhöhen, Zustand unverändert). Bei 11 nur normale Verarbeitung. Akzeptiert, wenn MM in Endzustand ist und genau zwei Nullen entfernt wurden.

Ihr Konstruktionsergebnis für M1M_1:
- Zustände: (q1,0)(q_1,0), (q1,1)(q_1,1), (q1,2)(q_1,2), (q2,0)(q_2,0), (q2,1)(q_2,1), (q2,2)(q_2,2), (q3,0)(q_3,0), (q3,1)(q_3,1), (q3,2)(q_3,2)
- Start: (q1,0)(q_1,0)
- Ende: (q3,2)(q_3,2)
- Transitionen (in Tripelform):
  (q1,0,0)(q2,0)(q_1,0,0) \to (q_2,0), (q1,0,0)(q1,1)(q_1,0,0) \to (q_1,1)
  (q1,1,0)(q2,1)(q_1,1,0) \to (q_2,1), (q1,1,0)(q1,2)(q_1,1,0) \to (q_1,2)
  (q1,2,0)(q2,2)(q_1,2,0) \to (q_2,2)
  (q2,0,0)(q3,0)(q_2,0,0) \to (q_3,0), (q2,0,0)(q2,1)(q_2,0,0) \to (q_2,1)
  (q2,0,1)(q1,0)(q_2,0,1) \to (q_1,0), (q2,0,1)(q3,0)(q_2,0,1) \to (q_3,0)
  (q2,1,0)(q3,1)(q_2,1,0) \to (q_3,1), (q2,1,0)(q2,2)(q_2,1,0) \to (q_2,2)
  (q2,1,1)(q1,1)(q_2,1,1) \to (q_1,1), (q2,1,1)(q3,1)(q_2,1,1) \to (q_3,1)
  (q2,2,0)(q3,2)(q_2,2,0) \to (q_3,2)
  (q2,2,1)(q1,2)(q_2,2,1) \to (q_1,2), (q2,2,1)(q3,2)(q_2,2,1) \to (q_3,2)
  (q3,0,0)(q3,1)(q_3,0,0) \to (q_3,1)
  (q3,0,1)(q2,0)(q_3,0,1) \to (q_2,0)
  (q3,1,0)(q3,2)(q_3,1,0) \to (q_3,2)
  (q3,1,1)(q2,1)(q_3,1,1) \to (q_2,1)
  (q3,2,1)(q2,2)(q_3,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
Die Aussage ist wahr: Für jede nichtleere Sprache LΣ L \subseteq \Sigma^*  gilt L0L L^{\uparrow 0} \neq L .

Beweis: Sei L L  eine nichtleere Sprache. Sei wL w \in L  ein Wort mit minimaler Anzahl an Nullen, sei m m  diese minimale Anzahl.

Fall 1: m<2 m < 2 . Dann hat w w  weniger als zwei Nullen. Aber jedes Wort in L0 L^{\uparrow 0}  hat mindestens zwei Nullen (da zwei Nullen eingefügt werden). Also ist wL0 w \notin L^{\uparrow 0} , aber wL w \in L , also L0L L^{\uparrow 0} \neq L .

Fall 2: m2 m \geq 2 . Dann hat w w  mindestens zwei Nullen. Angenommen, wL0 w \in L^{\uparrow 0} . Dann gibt es eine Zerlegung w=u0v0w w = u0v0w'  (wobei u,v,wΣ u,v,w' \in \Sigma^* ) und ein Wort x=uvwL x = u v w' \in L . Das Wort x x  hat m2 m - 2  Nullen (da wir zwei Nullen entfernen). Da m2 m \geq 2 , ist m20 m-2 \geq 0 , aber m2<m m-2 < m  (da m2 m \geq 2 ). Also hat x x  weniger Nullen als w w , nämlich m2 m-2 , was ein Widerspruch zur Minimalität von m m  ist. Also ist wL0 w \notin L^{\uparrow 0} , aber wL w \in L , also L0L L^{\uparrow 0} \neq L .

In beiden Fällen folgt die Behauptung.

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:

**Schritt 1: Entferne Zustand 1.**  
- Automat nach Entfernung:  
  - Zustände: 2, 3  
  - Startzustände: Übergang zu Zustand 2 mit "a", zu Zustand 3 mit "b"  
  - Finalzustände: 3  
  - Transitionen:  
    - Zustand 2 nach Zustand 2: "aa"  
    - Zustand 2 nach Zustand 3: "ab"  
    - Zustand 3 nach Zustand 3: "a"  
    - Zustand 3 nach Zustand 2: "b"  

**Schritt 2: Entferne Zustand 2.**  
- Automat nach Entfernung:  
  - Zustände: 3  
  - Startzustände: Übergang zu Zustand 3 mit "b" (direkt von Start) und mit "a(aa)*ab" (neu hinzugefügt)  
  - Finalzustände: 3  
  - Transitionen von Zustand 3 zu Zustand 3:  
    - "a" (vorhanden)  
    - "b(aa)*ab" (neu hinzugefügt)  

**Schritt 3: Entferne Zustand 3 (Finalzustand).**  
- Der reguläre Ausdruck wird aus den Startübergängen und den Schleifen am Finalzustand abgeleitet.  

Regulärer Ausdruck: $r = (b \mid a(aa)^{\ast}ab) (a \mid b(aa)^{\ast}ab)^{\ast}$

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 | b | bB
A -> aS
B -> aB | a | bA

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 (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:
SXCCDS \to X C \mid C D  
XaXbεX \to a X b \mid \varepsilon  
CaCεC \to a C \mid \varepsilon  
DbDaεD \to b D a \mid \varepsilon  

Grammatik für L2L_2:
SaSXaXTS \to a S X \mid a X T  
XabX \to a \mid b  
TaTbTεT \to a T \mid b T \mid \varepsilon  

Grammatik für L3L_3:
SXYS \to X Y  
XaXbXbεX \to a X b \mid X b \mid \varepsilon  
YbYabYbY \to b Y a \mid b Y \mid 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
Regulärer Ausdruck: a(ab)(ab)a(a|b)(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)
L_1: b
L_2: ab
L_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
Die Aussage ist wahr. Wir beweisen dies durch Widerspruch.

Angenommen, sowohl ABA \cup B als auch ABA \cup \overline{B} sind entscheidbar. Dann gilt:
A=(AB)(AB).
A = (A \cup B) \cap (A \cup \overline{B}).

Begründung:
- Ist xAx \in A, so ist xABx \in A \cup B und xABx \in A \cup \overline{B}, also x(AB)(AB)x \in (A \cup B) \cap (A \cup \overline{B}).
- Ist x(AB)(AB)x \in (A \cup B) \cap (A \cup \overline{B}), so folgt:  
  Wäre xAx \notin A, dann müsste xBx \in B (aus xABx \in A \cup B) und xBx \in \overline{B} (aus xABx \in A \cup \overline{B}) gelten, was unmöglich ist. Also ist xAx \in A.

Da die entscheidbaren Sprachen unter Schnitt abgeschlossen sind, ist (AB)(AB)(A \cup B) \cap (A \cup \overline{B}) entscheidbar. Somit wäre AA entscheidbar, im Widerspruch zur Voraussetzung. 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: 3SATpA\mathsf{3SAT} \le_p A
Begründung:
Gegeben eine Instanz von 3SAT\mathsf{3SAT}, d.h. eine 3KNF-Formel FF über einer Variablenmenge WW. Wir konstruieren eine Instanz von AA wie folgt: Die Variablenmenge sei V=WV = W. Definiere die drei KNF-Formeln:
- F1=FF_1 = F
- F2=FF_2 = F
- F3=F_3 = \bot, wobei \bot die unerfüllbare KNF-Formel ist, dargestellt durch eine einzelne leere Klausel (d.h., F3F_3 ist für alle Belegungen falsch).

Korrektheit der Reduktion:
- Wenn FF erfüllbar ist: Dann existiert eine Belegung σ:V{0,1}\sigma: V \to \{0,1\}, die FF erfüllt. Da F1=FF_1 = F und F2=FF_2 = F, erfüllt σ\sigma sowohl F1F_1 als auch F2F_2. Da F3=F_3 = \bot unerfüllbar ist, erfüllt σ\sigma F3F_3 nicht. Somit erfüllt σ\sigma genau zwei der drei Formeln (F1F_1 und F2F_2).
- Wenn FF unerfüllbar ist: Dann gibt es keine Belegung, die FF erfüllt, also erfüllt keine Belegung F1F_1 oder F2F_2. Zusätzlich ist F3=F_3 = \bot unerfüllbar, also erfüllt keine Belegung F3F_3. Daher erfüllt jede Belegung höchstens null Formeln (insbesondere nicht genau zwei).

Somit ist FF erfüllbar genau dann, wenn es eine Belegung gibt, die genau zwei der Formeln F1,F2,F3F_1, F_2, F_3 erfüllt. Die Reduktion ist polynomiell, da die Konstruktion nur das Kopieren von FF und das Erstellen der konstanten unerfüllbaren Formel F3F_3 erfordert.

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 von AA: eine 2KNF-Formel FF über Variablen V={x1,,xn}V = \{x_1, \dots, x_n\}, eine Farbmenge {1,,l}\{1, \dots, l\} und eine Färbung g:V{1,,l}g: V \to \{1, \dots, l\}. Wir konstruieren eine 2KNF-Formel FF' wie folgt:
F=F1i<jng(xi)=g(xj)(¬xi¬xj)
F' = F \land \bigwedge_{\substack{1 \leq i < j \leq n \\ g(x_i) = g(x_j)}} (\neg x_i \lor \neg x_j)

Die zusätzlichen Klauseln (¬xi¬xj)(\neg x_i \lor \neg x_j) für jedes Paar von Variablen xi,xjx_i, x_j mit gleicher Farbe (g(xi)=g(xj)g(x_i) = g(x_j)) stellen sicher, dass höchstens eine Variable pro Farbe auf 11 gesetzt werden kann. 

- Korrektheit:  
  - Wenn es eine erfüllende Belegung σ\sigma für FF gibt, die die Farbbedingung erfüllt (d.h., alle auf 11 gesetzten Variablen haben unterschiedliche Farben), dann erfüllt σ\sigma auch FF', da FF erfüllt ist und keine zwei Variablen gleicher Farbe beide auf 11 gesetzt sind, sodass alle hinzugefügten Klauseln erfüllt sind.  
  - Wenn FF' erfüllbar ist, dann erfüllt eine erfüllende Belegung σ\sigma sowohl FF als auch die zusätzlichen Klauseln. Letztere garantieren, dass für keine Farbe zwei Variablen beide auf 11 gesetzt sind, sodass die Farbbedingung erfüllt ist.  

Die Reduktion ist polynomiell, da die Anzahl der hinzugefügten Klauseln durch (n2)=O(n2)\binom{n}{2} = O(n^2) beschränkt ist und jede Klausel in konstanter Zeit konstruiert werden kann. Da 2SATP\mathsf{2SAT} \in \mathsf{P}, folgt 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 (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:
Angenommen, (L2)(L_2)^* sei regulär. Nach dem Pumping-Lemma existiert eine Pumping-Länge pp. Betrachte s=(apbp)p(L2)s = (a^p b^p)^p \in (L_2)^* mit s=2p2>p|s| = 2p^2 > p. Sei s=xyzs = xyz mit xyp|xy| \leq p, y>0|y| > 0. Da die ersten pp Symbole aa's sind, gilt y=aky = a^k für ein kk mit 1kp1 \leq k \leq p. Dann ist xy0z=apkbp(apbp)p1xy^0 z = a^{p-k} b^p (a^p b^p)^{p-1}. Dieses Wort ist nicht in (L2)(L_2)^*, da der Präfix apkbpa^{p-k} b^p nicht als Konkatenation von Wörtern aus L2L_2 zerlegt werden kann: Jeder Block in L2L_2 hat die Form ambma^m b^m, aber für apkbpa^{p-k} b^p mit pk<pp-k < p bleibt nach einem möglichen Block ambma^m b^m (mit mpkm \leq p-k) ein Suffix bpmapb^{p-m} a^p übrig, das nicht mit aa beginnt und somit keinen neuen Block starten kann. Widerspruch.

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 -> A3 D | D D  
D -> A3 A3  
A3 -> T A2  
A2 -> T T  
T -> 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 LLL'\subseteq L.Jede Sprache LLL'\subseteq L ist entscheidbar.
Begründung für Aussage 1:
Da LL kontextfrei und nicht regulär ist, muss LL unendlich sein (denn alle endlichen Sprachen sind regulär). Für jede unendliche Sprache LL existiert eine unentscheidbare Teilmenge LLL' \subseteq L. Dies folgt aus der Überabzählbarkeit der Potenzmenge von LL: Die Menge aller Teilmengen von LL ist überabzählbar, während die Menge der entscheidbaren Sprachen abzählbar ist (da es nur abzählbar viele Turingmaschinen gibt). Somit muss es überabzählbar viele unentscheidbare Teilmengen von LL geben. Insbesondere existiert also mindestens eine unentscheidbare Sprache LLL' \subseteq L.