Exam 2024_endterm.txt — google/gemini-2.5-pro

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 3.0/4.0 17.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 104.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=(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
Der gesuchte DFA MM' hat die folgende Spezifikation:
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:={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:
Die Menge SS enthält alle Zustände qq, die zu keinem anderen Zustand pp äquivalent sind. In der Äquivalenztabelle erkennt man diese Zustände daran, dass in der Zeile und Spalte, die dem Zustand qq entsprechen, kein Gleichheitszeichen „==" vorkommt. Dies ist für die Zustände 2 und 5 der Fall.

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.
<empty>
no answer given

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={wcwRanw{a,b}}L^{a^n}=\{w c w^R a^n \mid w \in \{a,b\}^*\}

Subproblem f (3.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 \ne j. Wir müssen zeigen, dass die Residualsprachen LwiL^{w_i} und LwjL^{w_j} verschieden sind.
Nach Definition ist wn=anw_n=a^n, also betrachten wir LaiL^{a^i} und LajL^{a^j}.

Die Residualsprache zu einem Wort uu ist definiert als Lu={v{a,b}uvL}L^u = \{v \in \{a,b\}^* \mid uv \in L\}.
Für u=aku=a^k besteht die Sprache LakL^{a^k} aus allen Wörtern vv, für die akvL={anbmn,m0nm}a^k v \in L = \{a^n b^m \mid n,m\ge0 \wedge n\ne m\} gilt.
Damit akva^k v die Form anbma^nb^m hat, muss vv von der Form bmb^m für ein m0m \ge 0 sein.
Die Bedingung nmn \ne m wird dann zu kmk \ne m.
Also ist die Residualsprache Lak={bmm0mk}L^{a^k} = \{b^m \mid m \ge 0 \land m \ne k\}.

Um zu beweisen, dass LaiLajL^{a^i} \ne L^{a^j} für iji \ne j, suchen wir ein Wort zz, das in einer der Sprachen liegt, aber nicht in der anderen. Wir wählen z=biz = b^i.

- Wir prüfen, ob zLaiz \in L^{a^i}:
Das Wort z=biz=b^i liegt in Lai={bmm0mi}L^{a^i} = \{b^m \mid m \ge 0 \land m \ne i\} genau dann, wenn m=im=i die Bedingung mim \ne i erfüllt. Dies ist offensichtlich falsch. Also biLaib^i \notin L^{a^i}.

- Wir prüfen, ob zLajz \in L^{a^j}:
Das Wort z=biz=b^i liegt in Laj={bmm0mj}L^{a^j} = \{b^m \mid m \ge 0 \land m \ne j\} genau dann, wenn m=im=i die Bedingung mjm \ne j erfüllt. Da wir iji \ne j angenommen haben, ist diese Bedingung wahr. Also biLajb^i \in L^{a^j}.

Da wir ein Wort z=biz=b^i gefunden haben, für das zLajz \in L^{a^j} und zLaiz \notin L^{a^i} gilt, sind die beiden Residualsprachen verschieden. Da dies für jedes Paar iji \ne j aus N\mathbb{N} gilt, gibt es unendlich viele paarweise verschiedene Residualsprachen.

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':=Q \times \{0,1,2\}
q0:=(q0,0)q_0':=(q_0, 0)
F:=F×{2}F':=F \times \{2\}

δ\delta':
Für einen Zustand (q,k)Q(q,k) \in Q' und ein Symbol xΣ{ϵ}x \in \Sigma \cup \{\epsilon\} ist δ((q,k),x)\delta'((q,k),x) wie folgt definiert:
*   Für aΣa \in \Sigma: δ((q,k),a):={(p,k)pδ(q,a)}\delta'((q,k), a) := \{ (p,k) \mid p \in \delta(q,a) \}
*   Für ϵ\epsilon:
    *   δ((q,k),ϵ):={(p,k+1)pδ(q,0)}\delta'((q,k), \epsilon) := \{ (p,k+1) \mid p \in \delta(q,0) \}, falls k{0,1}k \in \{0,1\}.
    *   δ((q,2),ϵ):=\delta'((q,2), \epsilon) := \emptyset.

Konstruktionsidee (optional):
Die Konstruktion ist eine Produktkonstruktion. Der neue Automat MM' besteht aus drei Kopien des ursprünglichen Automaten MM, die wir als Ebene 0, 1 und 2 bezeichnen. Ein Zustand in MM' ist ein Paar (q,k)(q,k), wobei qq ein Zustand aus MM ist und k{0,1,2}k \in \{0,1,2\} die Ebene angibt und gleichzeitig zählt, wie viele Nullen bereits aus der Eingabe "gelöscht" wurden.

*   Der Startzustand ist der Startzustand von MM auf Ebene 0, also (q0,0)(q_0,0).
*   Übergänge auf Symbolen aus Σ\Sigma finden nur innerhalb einer Ebene statt. Wenn es in MM einen Übergang qapq \xrightarrow{a} p gibt, gibt es in MM' für jede Ebene kk einen Übergang (q,k)a(p,k)(q,k) \xrightarrow{a} (p,k).
*   Das "Löschen" einer Null wird durch einen ϵ\epsilon-Übergang von einer Ebene zur nächsten simuliert. Für jeden Übergang q0pq \xrightarrow{0} p in MM gibt es in MM' ϵ\epsilon-Übergänge (q,0)ϵ(p,1)(q,0) \xrightarrow{\epsilon} (p,1) und (q,1)ϵ(p,2)(q,1) \xrightarrow{\epsilon} (p,2).
*   Die Endzustände von MM' sind die Endzustände von MM auf Ebene 2, also F×{2}F \times \{2\}. Dadurch wird sichergestellt, dass ein Wort nur dann akzeptiert wird, wenn genau zwei Nullen gelöscht wurden.

Ihr Konstruktionsergebnis für M1M_1:
Der resultierende NFA M1=(Q,Σ,δ,q0,F)M_1'=(Q',\Sigma,\delta',q_0',F') hat die folgenden Komponenten:

*   Zustände QQ': {(qi,j)i{1,2,3},j{0,1,2}}\{ (q_i, j) \mid i \in \{1,2,3\}, j \in \{0,1,2\} \}.
*   Startzustand q0q_0': (q1,0)(q_1, 0).
*   Finalzustände FF': {(q3,2)}\{ (q_3, 2) \}.
*   Transitionen δ\delta':
    *   Ebene 0:
        *   δ((q1,0),0)={(q2,0)}\delta'((q_1,0), 0) = \{(q_2,0)\}
        *   δ((q2,0),0)={(q3,0)}\delta'((q_2,0), 0) = \{(q_3,0)\}
        *   δ((q2,0),1)={(q1,0),(q3,0)}\delta'((q_2,0), 1) = \{(q_1,0), (q_3,0)\}
        *   δ((q3,0),1)={(q2,0)}\delta'((q_3,0), 1) = \{(q_2,0)\}
    *   Ebene 1:
        *   δ((q1,1),0)={(q2,1)}\delta'((q_1,1), 0) = \{(q_2,1)\}
        *   δ((q2,1),0)={(q3,1)}\delta'((q_2,1), 0) = \{(q_3,1)\}
        *   δ((q2,1),1)={(q1,1),(q3,1)}\delta'((q_2,1), 1) = \{(q_1,1), (q_3,1)\}
        *   δ((q3,1),1)={(q2,1)}\delta'((q_3,1), 1) = \{(q_2,1)\}
    *   Ebene 2:
        *   δ((q1,2),0)={(q2,2)}\delta'((q_1,2), 0) = \{(q_2,2)\}
        *   δ((q2,2),0)={(q3,2)}\delta'((q_2,2), 0) = \{(q_3,2)\}
        *   δ((q2,2),1)={(q1,2),(q3,2)}\delta'((q_2,2), 1) = \{(q_1,2), (q_3,2)\}
        *   δ((q3,2),1)={(q2,2)}\delta'((q_3,2), 1) = \{(q_2,2)\}
    *   ϵ\epsilon-Transitionen zwischen den Ebenen:
        *   δ((q1,0),ϵ)={(q2,1)}\delta'((q_1,0), \epsilon) = \{(q_2,1)\}
        *   δ((q2,0),ϵ)={(q3,1)}\delta'((q_2,0), \epsilon) = \{(q_3,1)\}
        *   δ((q1,1),ϵ)={(q2,2)}\delta'((q_1,1), \epsilon) = \{(q_2,2)\}
        *   δ((q2,1),ϵ)={(q3,2)}\delta'((q_2,1), \epsilon) = \{(q_3,2)\}

    Alle nicht explizit genannten Transitionen führen in die leere Menge.

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.

Beweis:
Wir führen einen Widerspruchsbeweis. Angenommen, es gibt eine nichtleere Sprache LΣL \subseteq \Sigma^*, für die L0=LL^{\uparrow 0} = L gilt.

Da LL nichtleer ist, enthält LL mindestens ein Wort. Die Menge der Längen aller Wörter in LL, also S={wwL}S = \{|w| \mid w \in L\}, ist eine nichtleere Teilmenge der natürlichen Zahlen (einschließlich 0). Nach dem Wohlordnungsprinzip besitzt jede nichtleere Teilmenge der natürlichen Zahlen ein kleinstes Element. Sei mm die minimale Länge eines Wortes in LL. Es gibt also ein Wort wminLw_{min} \in L mit wmin=m|w_{min}| = m, und für alle anderen Wörter wLw' \in L gilt wm|w'| \ge m.

Aus unserer Annahme L=L0L = L^{\uparrow 0} folgt insbesondere die Inklusion LL0L \subseteq L^{\uparrow 0}. Das bedeutet, jedes Wort in LL muss auch in L0L^{\uparrow 0} sein. Also muss auch unser Wort minimaler Länge, wminw_{min}, in L0L^{\uparrow 0} sein.

Per Definition von L0L^{\uparrow 0} bedeutet wminL0w_{min} \in L^{\uparrow 0}, dass es Wörter u,v,wΣu, v, w' \in \Sigma^* geben muss, sodass zwei Bedingungen erfüllt sind:
1. wmin=u0v0ww_{min} = u0v0w'
2. Das Wort wrem:=uvww_{rem} := uvw' ist ein Element von LL.

Betrachten wir nun die Länge des Wortes wremw_{rem}. Es gilt:
wrem=uvw=u+v+w|w_{rem}| = |uvw'| = |u| + |v| + |w'|.
Die Länge von wminw_{min} ist:
wmin=u0v0w=u+1+v+1+w=uvw+2=wrem+2|w_{min}| = |u0v0w'| = |u| + 1 + |v| + 1 + |w'| = |uvw'| + 2 = |w_{rem}| + 2.

Daraus folgt wrem=wmin2=m2|w_{rem}| = |w_{min}| - 2 = m - 2.
Wir haben also ein Wort wremw_{rem} gefunden, das in LL ist und die Länge m2m-2 hat. Da m2<mm-2 < m ist, widerspricht dies der Tatsache, dass mm die minimale Länge eines Wortes in LL ist.

Dieser Widerspruch beweist, dass unsere ursprüngliche Annahme falsch sein muss. Es kann also keine nichtleere Sprache LL geben, für die L=L0L = L^{\uparrow 0} gilt. Folglich muss für jede nichtleere Sprache LL die Ungleichung L0LL^{\uparrow 0} \neq L gelten.

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:
Der NFA wird zunächst um einen neuen Startzustand ss und einen neuen Endzustand ff erweitert. ss hat eine ε\varepsilon-Transition zum alten Startzustand 1. Alle alten Endzustände (hier nur 3) haben eine ε\varepsilon-Transition zum neuen Endzustand ff. Anschließend werden die Zustände 1, 2 und 3 in dieser Reihenfolge entfernt.

Initialer Automat nach Ergänzung um Start- und Endzustand:
*   Zustände: {s,1,2,3,f}\{s, 1, 2, 3, f\}
*   Startzustand: ss
*   Finalzustand: ff
*   Transitionen:
    *   (s,ε)1(s, \varepsilon) \to 1
    *   (1,a)2(1, a) \to 2
    *   (1,b)3(1, b) \to 3
    *   (2,a)1(2, a) \to 1
    *   (3,a)3(3, a) \to 3
    *   (3,b)2(3, b) \to 2
    *   (3,ε)f(3, \varepsilon) \to f

Nach Entfernen von Zustand 1:
Um Zustand 1 zu entfernen, werden für alle eingehenden Kanten (p,r1)1(p, r_1) \to 1 und ausgehenden Kanten (1,r2)q(1, r_2) \to q neue Kanten (p,r1(loop1)r2)q(p, r_1(\text{loop}_1)^*r_2) \to q hinzugefügt. Da Zustand 1 keine Schleife hat, ist (loop1)=ε=ε(\text{loop}_1)^* = \varepsilon^* = \varepsilon.
*   Pfad s12s \to 1 \to 2: Neue Kante (s,εεa)2(s, \varepsilon \varepsilon a) \to 2, vereinfacht zu (s,a)2(s, a) \to 2.
*   Pfad s13s \to 1 \to 3: Neue Kante (s,εεb)3(s, \varepsilon \varepsilon b) \to 3, vereinfacht zu (s,b)3(s, b) \to 3.
*   Pfad 2122 \to 1 \to 2: Neue Kante (2,aεa)2(2, a \varepsilon a) \to 2, also (2,aa)2(2, aa) \to 2.
*   Pfad 2132 \to 1 \to 3: Neue Kante (2,aεb)3(2, a \varepsilon b) \to 3, also (2,ab)3(2, ab) \to 3.
Der resultierende Automat ist:
*   Zustände: {s,2,3,f}\{s, 2, 3, f\}
*   Startzustand: ss
*   Finalzustand: ff
*   Transitionen:
    *   (s,a)2(s, a) \to 2
    *   (s,b)3(s, b) \to 3
    *   (2,aa)2(2, aa) \to 2
    *   (2,ab)3(2, ab) \to 3
    *   (3,a)3(3, a) \to 3
    *   (3,b)2(3, b) \to 2
    *   (3,ε)f(3, \varepsilon) \to f

Nach Entfernen von Zustand 2:
Zustand 2 hat eine Schleife mit dem Ausdruck aaaa. Der entsprechende Kleene-Stern ist (aa)(aa)^*.
*   Pfad s23s \to 2 \to 3: Die existierende Kante (s,b)3(s,b) \to 3 wird mit dem neuen Pfad über 2 kombiniert. Der neue Ausdruck für die Kante (s,3)(s,3) ist b+a(aa)abb + a(aa)^*ab.
*   Pfad 3233 \to 2 \to 3: Die existierende Schleife (3,a)3(3,a) \to 3 wird mit dem neuen Pfad über 2 kombiniert. Der neue Ausdruck für die Schleife auf 3 ist a+b(aa)aba + b(aa)^*ab.
Der resultierende Automat ist:
*   Zustände: {s,3,f}\{s, 3, f\}
*   Startzustand: ss
*   Finalzustand: ff
*   Transitionen:
    *   (s,b+a(aa)ab)3(s, b+a(aa)^*ab) \to 3
    *   (3,a+b(aa)ab)3(3, a+b(aa)^*ab) \to 3
    *   (3,ε)f(3, \varepsilon) \to f

Nach Entfernen von Zustand 3:
Zustand 3 hat eine Schleife mit dem Ausdruck a+b(aa)aba+b(aa)^*ab. Der entsprechende Kleene-Stern ist (a+b(aa)ab)(a+b(aa)^*ab)^*.
*   Pfad s3fs \to 3 \to f: Es wird eine Kante von ss nach ff mit dem Ausdruck (b+a(aa)ab)(a+b(aa)ab)ε(b+a(aa)^*ab)(a+b(aa)^*ab)^*\varepsilon erstellt, was sich zu (b+a(aa)ab)(a+b(aa)ab)(b+a(aa)^*ab)(a+b(aa)^*ab)^* vereinfacht.
Der resultierende Automat ist:
*   Zustände: {s,f}\{s, f\}
*   Startzustand: ss
*   Finalzustand: ff
*   Transitionen:
    *   (s,(b+a(aa)ab)(a+b(aa)ab))f(s, (b+a(aa)^*ab)(a+b(aa)^*ab)^*) \to f

Regulärer Ausdruck: r=(b+a(aa)ab)(a+b(aa)ab)r = (b+a(aa)^*ab)(a+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.
Eine rechtslineare Grammatik G=(V,Σ,P,S)G = (V, \Sigma, P, S) für die Sprache L(N)L(N) kann direkt aus dem NFA NN konstruiert werden. Die Nichtterminale VV der Grammatik entsprechen den Zuständen des NFA, und das Startsymbol SS entspricht dem Startzustand.

Seien die Nichtterminale X1,X2,X3X_1, X_2, X_3 den Zuständen 1, 2, 3 des NFA zugeordnet. Das Startsymbol ist X1X_1.
Die Produktionsregeln PP werden wie folgt aus den Transitionen des NFA abgeleitet:
1.  Für jede Transition (p,t)q(p, t) \to q wird eine Regel XptXqX_p \to t X_q erzeugt.
2.  Wenn der Zielzustand qq ein Finalzustand ist, wird zusätzlich eine Regel XptX_p \to t erzeugt.

Anwendung auf den gegebenen NFA NN:
*   Zustand 1 (Startsymbol X1X_1):
    *   Transition (1,a)2(1, a) \to 2: ergibt die Regel X1aX2X_1 \to a X_2.
    *   Transition (1,b)3(1, b) \to 3: Da Zustand 3 ein Finalzustand ist, ergeben sich die Regeln X1bX3X_1 \to b X_3 und X1bX_1 \to b.
    *   Zusammengefasst für X1X_1: X1aX2bX3bX_1 \to a X_2 \mid b X_3 \mid b

*   Zustand 2 (Nichtterminal X2X_2):
    *   Transition (2,a)1(2, a) \to 1: ergibt die Regel X2aX1X_2 \to a X_1.

*   Zustand 3 (Nichtterminal X3X_3):
    *   Transition (3,a)3(3, a) \to 3: Da Zustand 3 ein Finalzustand ist, ergeben sich die Regeln X3aX3X_3 \to a X_3 und X3aX_3 \to a.
    *   Transition (3,b)2(3, b) \to 2: ergibt die Regel X3bX2X_3 \to b X_2.
    *   Zusammengefasst für X3X_3: X3aX3bX2aX_3 \to a X_3 \mid b X_2 \mid a

Die resultierende rechtslineare Grammatik mit 3 Nichtterminalen (X1,X2,X3X_1, X_2, X_3) ist:
X1aX2bX3bX_1 \to aX_2 \mid bX_3 \mid b
X2aX1X_2 \to aX_1
X3aX3bX2aX_3 \to aX_3 \mid bX_2 \mid a
0: could not parse value
    Eine rechtslineare Grammatik $G = (V, \Sigma, P, S)$ für die Sprache $L(N)$ kann direkt aus dem NFA $N$ konstruiert werden. Die Nichtterminale $V$ der Grammatik entsprechen den Zuständen des NFA, und das Startsymbol $S$ entspricht dem Startzustand.
    
    Seien die Nichtterminale $X_1, X_2, X_3$ den Zuständen 1, 2, 3 des NFA zugeordnet. Das Startsymbol ist $X_1$.
    Die Produktionsregeln $P$ werden wie folgt aus den Transitionen des NFA abgeleitet:
    1.  Für jede Transition $(p, t) \to q$ wird eine Regel $X_p \to t X_q$ erzeugt.
    2.  Wenn der Zielzustand $q$ ein Finalzustand ist, wird zusätzlich eine Regel $X_p \to t$ erzeugt.
    
    Anwendung auf den gegebenen NFA $N$:
    *   **Zustand 1 (Startsymbol $X_1$):**
        *   Transition $(1, a) \to 2$: ergibt die Regel $X_1 \to a X_2$.
        *   Transition $(1, b) \to 3$: Da Zustand 3 ein Finalzustand ist, ergeben sich die Regeln $X_1 \to b X_3$ und $X_1 \to b$.
        *   Zusammengefasst für $X_1$: $X_1 \to a X_2 \mid b X_3 \mid b$
    
    *   **Zustand 2 (Nichtterminal $X_2$):**
        *   Transition $(2, a) \to 1$: ergibt die Regel $X_2 \to a X_1$.
    
    *   **Zustand 3 (Nichtterminal $X_3$):**
        *   Transition $(3, a) \to 3$: Da Zustand 3 ein Finalzustand ist, ergeben sich die Regeln $X_3 \to a X_3$ und $X_3 \to a$.
        *   Transition $(3, b) \to 2$: ergibt die Regel $X_3 \to b X_2$.
        *   Zusammengefasst für $X_3$: $X_3 \to a X_3 \mid b X_2 \mid a$
    
    Die resultierende rechtslineare Grammatik mit 3 Nichtterminalen ($X_1, X_2, X_3$) ist:
    $X_1 \to aX_2 \mid bX_3 \mid b$
    $X_2 \to aX_1$
    $X_3 \to aX_3 \mid bX_2 \mid a$
for type cfg

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:
SXCCYS \to XC \mid CY
XaXbεX \to aXb \mid \varepsilon
YbYaεY \to bYa \mid \varepsilon
CaCεC \to aC \mid \varepsilon

Grammatik für L2L_2:
SARS \to AR
AaAaaAbaaabA \to aAa \mid aAb \mid aa \mid ab
RaRbRεR \to aR \mid bR \mid \varepsilon

Grammatik für L3L_3:
SABCS \to ABC
AaAbεA \to aAb \mid \varepsilon
BbBbB \to bB \mid b
CbCaεC \to bCa \mid \varepsilon

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)
Wort, falls LiLϵ(M)L_i\neq L_\epsilon(M), sonst „-“.
L1L_1: b
L2L_2: b
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
Die Aussage ist wahr.

Beweis:
Wir führen einen Widerspruchsbeweis. Angenommen, die Aussage sei falsch. Das würde bedeuten, dass es eine unentscheidbare Sprache AA und eine Sprache BB gibt, für die sowohl ABA \cup B als auch ABA \cup \overline{B} entscheidbar sind.

Seien L1=ABL_1 = A \cup B und L2=ABL_2 = A \cup \overline{B}. Nach unserer Annahme sind L1L_1 und L2L_2 entscheidbare Sprachen.

Die Klasse der entscheidbaren Sprachen ist unter der Schnittmengenbildung abgeschlossen. Das bedeutet, wenn L1L_1 und L2L_2 entscheidbar sind, dann ist auch ihre Schnittmenge L1L2L_1 \cap L_2 entscheidbar.

Betrachten wir nun die Menge L1L2L_1 \cap L_2. Mithilfe der Distributivgesetze der Mengenlehre können wir den Ausdruck vereinfachen:
L1L2=(AB)(AB)=A(BB) L_1 \cap L_2 = (A \cup B) \cap (A \cup \overline{B}) = A \cup (B \cap \overline{B}) 
Der Schnitt einer Sprache BB mit ihrem Komplement B\overline{B} ist immer die leere Menge, d.h. BB=B \cap \overline{B} = \emptyset.
Somit gilt:
L1L2=A=A L_1 \cap L_2 = A \cup \emptyset = A 
Wir haben also gezeigt, dass die Sprache AA identisch ist mit der Sprache L1L2L_1 \cap L_2. Da L1L_1 und L2L_2 entscheidbar sind, muss auch ihr Schnitt AA entscheidbar sein.

Dies steht jedoch im Widerspruch zur Voraussetzung, dass AA unentscheidbar ist.
Unsere Annahme, dass sowohl ABA \cup B als auch ABA \cup \overline{B} entscheidbar sind, muss daher falsch sein. Folglich muss mindestens eine der beiden Sprachen 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:
Wir zeigen, dass das Problem AA NP\mathsf{NP}-hart ist, indem wir das bekannte NP\mathsf{NP}-harte Problem SAT\mathsf{SAT} polynomiell auf AA reduzieren.

Sei Φ\Phi eine beliebige KNF-Formel über einer Variablenmenge VV, die eine Instanz von SAT\mathsf{SAT} ist. Wir konstruieren daraus eine Instanz von Problem AA, also drei KNF-Formeln (F1,F2,F3)(F_1, F_2, F_3), wie folgt:
- F1:=ΦF_1 := \Phi
- F2:=(x¬x)F_2 := (x \lor \neg x), wobei xx eine beliebige Variable ist (z.B. eine aus VV oder eine neue). Dies ist eine Tautologie.
- F3:=(x¬x)F_3 := (x \land \neg x), was der KNF-Formel (x)(¬x)(x) \land (\neg x) entspricht. Dies ist ein Widerspruch.

Diese Reduktion ist in Polynomialzeit durchführbar, da die erzeugten Formeln F2F_2 und F3F_3 konstante Größe haben und F1F_1 einfach die Eingabeformel Φ\Phi ist.

Korrektheit der Reduktion:
Wir müssen zeigen, dass Φ\Phi genau dann erfüllbar ist, wenn es eine Belegung σ\sigma gibt, die genau zwei der Formeln F1,F2,F3F_1, F_2, F_3 erfüllt.

(\Rightarrow) Angenommen, Φ\Phi ist erfüllbar. Sei σ\sigma eine erfüllende Belegung für Φ\Phi.
- σ\sigma erfüllt F1F_1, da F1=ΦF_1 = \Phi.
- σ\sigma erfüllt F2F_2, da F2F_2 eine Tautologie ist und von jeder Belegung erfüllt wird.
- σ\sigma erfüllt F3F_3 nicht, da F3F_3 ein Widerspruch ist und von keiner Belegung erfüllt werden kann.
Somit erfüllt σ\sigma genau zwei Formeln, nämlich F1F_1 und F2F_2. Die Antwort für die Instanz (F1,F2,F3)(F_1, F_2, F_3) von Problem AA ist also "Ja".

(\Leftarrow) Angenommen, es gibt eine Belegung σ\sigma, die genau zwei der Formeln F1,F2,F3F_1, F_2, F_3 erfüllt. Es gibt drei Möglichkeiten:
1.  σ\sigma erfüllt F1F_1 und F2F_2, aber nicht F3F_3. Da σ\sigma die Formel F1=ΦF_1 = \Phi erfüllt, ist Φ\Phi erfüllbar.
2.  σ\sigma erfüllt F1F_1 und F3F_3, aber nicht F2F_2. Dieser Fall kann nicht eintreten, da keine Belegung die widersprüchliche Formel F3F_3 erfüllen kann.
3.  σ\sigma erfüllt F2F_2 und F3F_3, aber nicht F1F_1. Dieser Fall kann ebenfalls nicht eintreten, da F3F_3 unerfüllbar ist.

Da nur der erste Fall möglich ist, muss Φ\Phi erfüllbar sein, wenn die Instanz von AA eine "Ja"-Instanz ist.

Zusammenfassend ist Φ\Phi genau dann erfüllbar, wenn die konstruierte Instanz von AA eine "Ja"-Antwort hat. Da SAT\mathsf{SAT} NP\mathsf{NP}-hart ist, ist somit auch das Problem AA NP\mathsf{NP}-hart.

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:
Wir zeigen, dass das Problem AA in P\mathsf{P} liegt, indem wir es polynomiell auf das Problem 2KNF-SAT\mathsf{2KNF\text{-}SAT} reduzieren, welches bekanntlich in P\mathsf{P} ist.

Sei (F,g)(F, g) eine Instanz von Problem AA, wobei FF eine 2KNF-Formel über der Variablenmenge V={x1,...,xn}V=\{x_1, ..., x_n\} ist und g:V{1,...,l}g: V \to \{1, ..., l\} eine Farbfunktion. Die Bedingung des Problems ist, dass in einer erfüllenden Belegung σ\sigma von FF alle Variablen, die auf Wahr gesetzt werden, unterschiedliche Farben haben müssen. Dies ist äquivalent zu der Aussage, dass für jedes Paar von Variablen xi,xjx_i, x_j mit der gleichen Farbe (g(xi)=g(xj)g(x_i)=g(x_j)) nicht beide gleichzeitig auf Wahr gesetzt werden dürfen. Diese Bedingung lässt sich durch die logische Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) ausdrücken.

Wir konstruieren eine neue 2KNF-Formel FF' wie folgt:
FF' ist die Konjunktion von FF und einer Menge von neuen Klauseln FgF_g. Die Menge FgF_g wird wie folgt gebildet: Für jedes Paar von verschiedenen Variablen (xi,xj)(x_i, x_j) mit iji \neq j, für die g(xi)=g(xj)g(x_i) = g(x_j) gilt, fügen wir die Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) zu FgF_g hinzu.
Die resultierende Formel ist F=FCFgCF' = F \land \bigwedge_{C \in F_g} C.
Da FF eine 2KNF-Formel ist und alle Klauseln in FgF_g ebenfalls 2-Klauseln sind, ist FF' eine 2KNF-Formel.

Die Reduktion ist in Polynomialzeit durchführbar. Die Anzahl der Variablen ist nn. Es gibt (n2)\binom{n}{2} Paare von Variablen. Für jedes Paar prüfen wir, ob die Farben gleich sind und fügen gegebenenfalls eine Klausel hinzu. Die Größe von FF' ist also polynomiell in der Größe der Eingabe.

Korrektheit der Reduktion:
Wir skizzieren, warum die Instanz (F,g)(F, g) von AA eine Ja-Antwort hat genau dann, wenn die Formel FF' erfüllbar ist.

(\Rightarrow) Angenommen, es gibt eine erfüllende Belegung σ\sigma für FF, die die Farbbedingung erfüllt.
- σ\sigma erfüllt per Definition alle Klauseln in FF.
- Betrachten wir eine Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) aus FgF_g. Sie wurde hinzugefügt, weil g(xi)=g(xj)g(x_i)=g(x_j). Da σ\sigma die Farbbedingung erfüllt, kann nicht gleichzeitig σ(xi)=1\sigma(x_i)=1 und σ(xj)=1\sigma(x_j)=1 gelten. Also ist mindestens eine der Variablen auf 0 gesetzt, was die Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) wahr macht.
- Somit erfüllt σ\sigma alle Klauseln in FF', also ist FF' erfüllbar.

(\Leftarrow) Angenommen, FF' ist erfüllbar und sei σ\sigma eine erfüllende Belegung.
- Da FF' die Konjunktion von FF und FgF_g ist, muss σ\sigma sowohl FF als auch alle Klauseln in FgF_g erfüllen.
- Dass σ\sigma FF erfüllt, ist die erste Bedingung für eine Lösung von AA.
- Dass σ\sigma alle Klauseln in FgF_g erfüllt, bedeutet, dass für jedes Paar xi,xjx_i, x_j mit g(xi)=g(xj)g(x_i)=g(x_j) die Klausel (¬xi¬xj)(\neg x_i \lor \neg x_j) wahr ist. Dies impliziert, dass nicht beide, σ(xi)\sigma(x_i) und σ(xj)\sigma(x_j), 1 sein können. Dies ist genau die Farbbedingung des Problems AA.
- Also ist σ\sigma eine gültige Lösung für die Instanz (F,g)(F, g) von AA.

Da AA auf 2KNF-SAT\mathsf{2KNF\text{-}SAT} polynomiell reduzierbar ist und 2KNF-SATP\mathsf{2KNF\text{-}SAT} \in \mathsf{P}, liegt auch AA in P\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:
Wir beweisen mittels des Pumping-Lemmas für reguläre Sprachen, dass (L2)(L_2)^* nicht regulär ist.
Sei L:=(L2)=({anbn:nN})L := (L_2)^* = (\{a^n b^n : n \in \mathbb{N}\})^*.

Annahme: LL ist eine reguläre Sprache. Sei pp die Pumping-Länge gemäß dem Pumping-Lemma.

Wir wählen das Wort w:=apbpw := a^p b^p.
Da wL2w \in L_2 und per Definition L2LL_2 \subseteq L, ist auch wLw \in L.
Weiterhin gilt w=2pp|w| = 2p \ge p.

Nach dem Pumping-Lemma kann ww in drei Teile x,y,zx, y, z zerlegt werden, d.h. w=xyzw=xyz, sodass die folgenden Bedingungen erfüllt sind:
1. xyp|xy| \le p
2. y1|y| \ge 1
3. Für alle i0i \ge 0 gilt xyizLxy^iz \in L.

Aufgrund der Bedingung xyp|xy| \le p und der Struktur von w=apbpw = a^p b^p muss der Teilstring yy ausschließlich aus dem Symbol 'a' bestehen. Es gilt also y=aky = a^k für eine ganze Zahl k1k \ge 1 (wegen y1|y| \ge 1).

Wir betrachten nun das "herausgepumpte" Wort für i=0i=0, also w=xy0z=xzw' = xy^0z = xz.
Dieses Wort hat die Form apkbpa^{p-k}b^p.
Laut Pumping-Lemma muss wLw' \in L gelten.

Ein Wort liegt in L=(L2)L=(L_2)^*, wenn es eine Konkatenation von Wörtern aus L2={ε,ab,aabb,}L_2 = \{\varepsilon, ab, aabb, \dots\} ist. Jedes nicht-leere Wort in L2L_2 hat die Form anbna^n b^n für n1n \ge 1. Die Konkatenation von zwei oder mehr nicht-leeren Wörtern aus L2L_2 (z.B. (an1bn1)(an2bn2)(a^{n_1}b^{n_1})(a^{n_2}b^{n_2}) mit n1,n21n_1, n_2 \ge 1) enthält zwingend den Teilstring "ba".
Das Wort w=apkbpw' = a^{p-k}b^p enthält jedoch kein "ba". Damit ww' in LL liegen kann, muss es entweder das leere Wort sein (was nicht der Fall ist, da p1p \ge 1) oder selbst ein Element von L2L_2 sein.

Damit w=apkbpw' = a^{p-k}b^p in L2L_2 liegt, muss die Anzahl der 'a's gleich der Anzahl der 'b's sein. Es muss also pk=pp-k = p gelten. Dies impliziert k=0k=0.
Dies steht jedoch im Widerspruch zur Bedingung y=k1|y| = k \ge 1 des Pumping-Lemmas.

Somit führt die Annahme, dass (L2)(L_2)^* regulär ist, zu einem Widerspruch. Folglich 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:
Ja, eine solche Grammatik G=(V,Σ,R,S)G = (V, \Sigma, R, S) existiert.
Sei Σ={a}\Sigma = \{a\} und V={S,A,A2,A4,A8}V = \{S, A, A_2, A_4, A_8\}.
Die Menge der Produktionen RR ist:
SA8A4S \to A_8 A_4
SA8AS \to A_8 A
A8A4A4A_8 \to A_4 A_4
A4A2A2A_4 \to A_2 A_2
A2AAA_2 \to A A
AaA \to a

Diese Grammatik hat 6 Produktionen und ist in Chomsky-Normalform, da jede Regel die Form ABCA \to BC oder AaA \to a hat.

Herleitung der Sprache L(G)L(G):
- AA leitet das Wort a1=aa^1=a ab.
- A2AAA_2 \to AA leitet a1a1=a2a^1a^1 = a^2 ab.
- A4A2A2A_4 \to A_2A_2 leitet a2a2=a4a^2a^2 = a^4 ab.
- A8A4A4A_8 \to A_4A_4 leitet a4a4=a8a^4a^4 = a^8 ab.
- Die erste Startregel SA8A4S \to A_8A_4 leitet a8a4=a12a^8a^4 = a^{12} ab.
- Die zweite Startregel SA8AS \to A_8A leitet a8a1=a9a^8a^1 = a^9 ab.

Somit ist die von der Grammatik erzeugte Sprache L(G)={a12,a9}L(G) = \{a^{12}, a^9\}.
0: could not parse value
    Ja, eine solche Grammatik G = (V, \Sigma, R, S) existiert.
    Sei \Sigma = \{a\} und V = \{S, A, A_2, A_4, A_8\}.
    Die Menge der Produktionen R ist:
    S \to A_8 A_4
    S \to A_8 A
    A_8 \to A_4 A_4
    A_4 \to A_2 A_2
    A_2 \to A A
    A \to a
    
    Diese Grammatik hat 6 Produktionen und ist in Chomsky-Normalform, da jede Regel die Form A \to BC oder A \to a hat.
    
    Herleitung der Sprache L(G):
    - A leitet das Wort a^1=a ab.
    - A_2 \to AA leitet a^1a^1 = a^2 ab.
    - A_4 \to A_2A_2 leitet a^2a^2 = a^4 ab.
    - A_8 \to A_4A_4 leitet a^4a^4 = a^8 ab.
    - Die erste Startregel S \to A_8A_4 leitet a^8a^4 = a^{12} ab.
    - Die zweite Startregel S \to A_8A leitet a^8a^1 = a^9 ab.
    
    Somit ist die von der Grammatik erzeugte Sprache L(G) = \{a^{12}, a^9\}.
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:
Eine Sprache LL ist genau dann regulär, wenn sie von einem endlichen Automaten akzeptiert wird. Jede endliche Sprache ist regulär, da man für sie einen endlichen Automaten konstruieren kann, der genau die (endlich vielen) Wörter der Sprache akzeptiert. Da die gegebene Sprache LL als nicht regulär vorausgesetzt wird, muss sie unendlich viele Wörter enthalten.

Da L{0,1}L \subseteq \{0,1\}^* gilt und {0,1}\{0,1\}^* eine abzählbar unendliche Menge ist, ist auch LL eine abzählbar unendliche Menge.

Betrachten wir nun die Menge aller Teilmengen von LL, also die Potenzmenge P(L)\mathcal{P}(L). Nach dem Satz von Cantor ist die Potenzmenge einer abzählbar unendlichen Menge überabzählbar unendlich. Es gibt also überabzählbar viele verschiedene Sprachen LL', die Teilmengen von LL sind.

Andererseits ist die Menge aller entscheidbaren Sprachen über dem Alphabet {0,1}\{0,1\}^* nur abzählbar unendlich. Das liegt daran, dass jede entscheidbare Sprache durch eine Turing-Maschine (die immer hält) entschieden wird. Die Menge aller Turing-Maschinen ist abzählbar, da jede Turing-Maschine als endlicher String kodiert werden kann.

Wir haben also eine überabzählbare Menge von Teilmengen von LL, aber nur eine abzählbare Menge von entscheidbaren Sprachen. Selbst wenn jede entscheidbare Sprache eine Teilmenge von LL wäre (was nicht der Fall ist), gäbe es immer noch nicht "genug" entscheidbare Sprachen, um alle Teilmengen von LL abzudecken.

Daraus folgt zwingend, dass es Teilmengen LLL' \subseteq L geben muss, die nicht entscheidbar sind. Gäbe es keine solche unentscheidbare Teilmenge, wären alle Teilmengen von LL entscheidbar. Dann wäre die überabzählbare Menge P(L)\mathcal{P}(L) eine Teilmenge der abzählbaren Menge der entscheidbaren Sprachen, was ein Widerspruch ist.

Somit ist die Existenz einer unentscheidbaren Sprache LLL' \subseteq L bewiesen.