anthropic/claude-opus-4.1

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (0.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:
Angenommen, die Sprache L={aibjck:(i1j=k)i,j,k0}L = \{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\} ist regulär. Dann existiert eine Pumping-Länge pp.

Betrachte den String w=abpcpw = ab^pc^p. Es gilt w=1+2pp|w| = 1 + 2p \ge p und wLw \in L, da i=1i=1 und j=k=pj=k=p, also die Bedingung (i1j=k)(i\ne 1\vee j=k) erfüllt ist.

Nach dem Pumping-Lemma kann w=xyzw = xyz geschrieben werden mit:
1. xyp|xy| \le p
2. y>0|y| > 0  
3. Für alle n0n \ge 0 gilt xynzLxy^nz \in L

Da xyp|xy| \le p und der String mit aa beginnt gefolgt von pp b's, besteht xyxy aus dem aa und höchstens p1p-1 b's.

Da y>0|y| > 0 und yy ein Teilstring von xyxy ist, muss y=bmy = b^m für ein m>0m > 0 gelten (da wir nur ein aa haben und xyp|xy| \le p).

Dann ist x=ax = a und z=bpmcpz = b^{p-m}c^p.

Für n=0n = 0 erhalten wir:
xy0z=abpmcpxy^0z = ab^{p-m}c^p

Dieser String hat i=1i=1, j=pmj=p-m und k=pk=p. Damit er in LL ist, muss (11pm=p)(1\ne 1\vee p-m=p) gelten, was zu pm=pp-m=p führt. Dies ist falsch, da m>0m > 0.

Also ist xy0zLxy^0z \notin L, was dem Pumping-Lemma widerspricht.

Daher ist LL nicht regulär.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: baba
2: -
3: baabaa

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Wir zeigen, dass L1={wΣ:L(Mw)2=25}L_1 = \{w\in\Sigma^*:|L(M_w)|^2=25\} unentscheidbar ist mittels Rice's Theorem.

Die Sprache L1L_1 entspricht der Menge aller Turingmaschinen-Kodierungen, deren akzeptierte Sprache genau 5 Elemente enthält (da L(Mw)2=25L(Mw)=5|L(M_w)|^2 = 25 \Rightarrow |L(M_w)| = 5).

Nach Rice's Theorem ist jede nicht-triviale Eigenschaft von Sprachen, die von Turingmaschinen erkannt werden, unentscheidbar. Eine Eigenschaft PP ist nicht-trivial, wenn:
1. Es mindestens eine Turingmaschine gibt, deren Sprache die Eigenschaft PP hat
2. Es mindestens eine Turingmaschine gibt, deren Sprache die Eigenschaft PP nicht hat

Für die Eigenschaft "L=5|L| = 5":
1. Existenz einer TM mit der Eigenschaft: Konstruiere eine TM M1M_1, die genau die Strings {0,1,00,01,10}\{0, 1, 00, 01, 10\} akzeptiert. Diese TM prüft einfach, ob die Eingabe einem dieser 5 Strings entspricht und akzeptiert genau dann. Also gilt L(M1)=5|L(M_1)| = 5.

2. Existenz einer TM ohne die Eigenschaft: Konstruiere eine TM M2M_2, die alle Strings akzeptiert (d.h. L(M2)=ΣL(M_2) = \Sigma^*). Da Σ\Sigma^* unendlich ist, gilt L(M2)=5|L(M_2)| = \infty \ne 5.

Da die Eigenschaft "L=5|L| = 5" nicht-trivial ist, folgt aus Rice's Theorem, dass L1={wΣ:L(Mw)2=25}L_1 = \{w\in\Sigma^*:|L(M_w)|^2=25\} unentscheidbar ist.

anthropic/claude-sonnet-4

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:

Sei L={aibjck:(i1j=k)i,j,k0}L = \{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}.

Angenommen LL ist regulär. Da reguläre Sprachen unter Durchschnitt abgeschlossen sind und abcab^*c^* regulär ist, wäre auch LabcL \cap ab^*c^* regulär.

Berechnen wir LabcL \cap ab^*c^*:
Labc={abjck:(11j=k)j,k0}L \cap ab^*c^* = \{ab^jc^k : (1 \neq 1 \vee j = k) \wedge j,k \geq 0\}

Da 111 \neq 1 falsch ist, reduziert sich die Bedingung zu j=kj = k:
Labc={abjcj:j0}L \cap ab^*c^* = \{ab^jc^j : j \geq 0\}

Diese Sprache ist jedoch nicht regulär. Dies kann mit dem Pumping-Lemma gezeigt werden:

Sei pp die Pumping-Länge und betrachte das Wort w=abpcpLabcw = ab^pc^p \in L \cap ab^*c^*.
Nach dem Pumping-Lemma existiert eine Zerlegung w=xyzw = xyz mit xyp|xy| \leq p, y>0|y| > 0, sodass xyizLabcxy^iz \in L \cap ab^*c^* für alle i0i \geq 0.

Da xyp|xy| \leq p und ww mit aa beginnt, gefolgt von pp Kopien von bb, muss y=bky = b^k für ein k>0k > 0 sein.

Dann ist xy0z=abpkcpxy^0z = ab^{p-k}c^p. Für dieses Wort gilt j=pkp=kj = p-k \neq p = k, also ist xy0zLabcxy^0z \notin L \cap ab^*c^*.

Dies ist ein Widerspruch, also ist LabcL \cap ab^*c^* nicht regulär.

Da der Durchschnitt einer regulären Sprache mit einer regulären Sprache regulär sein muss, kann LL nicht regulär sein.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: aabaab
2: -
3: bababaabababaa

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:

Wir zeigen, dass die Sprache L1={wΣ:L(Mw)=5}L_1 = \{w\in\Sigma^*:|L(M_w)|=5\} unentscheidbar ist, indem wir das Halteproblem auf L1L_1 reduzieren.

Das Halteproblem ist: Gegeben eine Turingmaschine MM und eine Eingabe xx, hält MM bei Eingabe xx?

Sei (M,x)(M,x) eine Instanz des Halteproblems. Wir konstruieren eine Turingmaschine MM', sodass:
- Falls MM bei Eingabe xx hält, dann L(M)=5|L(M')| = 5
- Falls MM bei Eingabe xx nicht hält, dann L(M)5|L(M')| \neq 5

Konstruktion von MM':
MM' bei Eingabe ww:
1. Falls w{0,00,000,0000}w \in \{0, 00, 000, 0000\}, akzeptiere.
2. Falls w=1w = 1, simuliere MM auf Eingabe xx. Falls MM hält, akzeptiere. Andernfalls laufe unendlich.
3. Für alle anderen Eingaben, verwerfe.

Analyse:
- Falls MM bei Eingabe xx hält: L(M)={0,00,000,0000,1}L(M') = \{0, 00, 000, 0000, 1\}, also L(M)=5|L(M')| = 5.
- Falls MM bei Eingabe xx nicht hält: L(M)={0,00,000,0000}L(M') = \{0, 00, 000, 0000\}, also L(M)=45|L(M')| = 4 \neq 5.

Damit gilt: (M,x)(M,x) \in Halteproblem ML1\Leftrightarrow \langle M' \rangle \in L_1.

Da das Halteproblem unentscheidbar ist und wir eine Reduktion vom Halteproblem auf L1L_1 konstruiert haben, ist L1L_1 unentscheidbar.

deepseek/deepseek-chat-v3.1

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:
Angenommen, die Sprache L = { a^i b^j c^k : (i ≠ 1 ∨ j = k) ∧ i,j,k ≥ 0 } sei regulär. Betrachte die reguläre Sprache R = { a b^j c^k : j,k ≥ 0 }. Da reguläre Sprachen unter Schnitt abgeschlossen sind, müsste L ∩ R regulär sein.

Es gilt: L ∩ R = { a b^j c^k : (i ≠ 1 ∨ j = k) ∧ i = 1 } = { a b^j c^k : j = k } = { a b^j c^j : j ≥ 0 }.

Diese Sprache ist nicht regulär. Zum Beweis verwenden wir das Pumping-Lemma: Angenommen, { a b^j c^j : j ≥ 0 } sei regulär. Sei p die Pumping-Länge. Betrachte das Wort s = a b^p c^p. Nach dem Pumping-Lemma kann s in xyz zerlegt werden mit |xy| ≤ p, |y| > 0, und für alle i ≥ 0 gilt xy^i z ∈ { a b^j c^j : j ≥ 0 }.

Da |xy| ≤ p und s mit a beginnt, gefolgt von b's, besteht y nur aus b's. Dann ist für i = 0 das Wort xy^0 z = a b^{p-|y|} c^p. Da |y| > 0, ist p - |y| < p, also die Anzahl der b's ungleich der Anzahl der c's, somit xy^0 z nicht in { a b^j c^j : j ≥ 0 }, Widerspruch.

Daher ist L ∩ R nicht regulär, was der Annahme widerspricht, dass L regulär ist. Also ist L nicht regulär.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: ab
2: -
3: baa

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Angenommen, die Sprache L={wΣ:L(Mw)2=25} L = \{ w \in \Sigma^* : |L(M_w)|^2 = 25 \}  sei entscheidbar. Da L(Mw)2=25 |L(M_w)|^2 = 25  genau dann gilt, wenn L(Mw)=5 |L(M_w)| = 5 , ist L L  äquivalent zu {w:L(Mw)=5} \{ w : |L(M_w)| = 5 \} .

Wir reduzieren das Halteproblem auf L L . Das Halteproblem H={M,x:M ha¨lt auf Eingabe x} H = \{ \langle M, x \rangle : M \text{ hält auf Eingabe } x \}  ist unentscheidbar.

Für eine gegebene Turingmaschine M M  und Eingabe x x  konstruieren wir eine Turingmaschine M M'  wie folgt: M M'  ignoriert ihre eigene Eingabe y y  und simuliert zunächst M M  auf x x . Wenn M M  auf x x  hält, dann akzeptiert M M'  genau dann, wenn y y  zu einer festen Menge von fünf Strings gehört, z.B. S={ε,0,1,00,01} S = \{ \varepsilon, 0, 1, 00, 01 \} . Wenn M M  auf x x  nicht hält, dann hält M M'  nie, also akzeptiert sie keine Strings.

Somit gilt:
- Wenn M M  auf x x  hält, dann L(M)=S L(M') = S , also L(M)=5 |L(M')| = 5 .
- Wenn M M  auf x x  nicht hält, dann L(M)= L(M') = \emptyset , also L(M)=05 |L(M')| = 0 \neq 5 .

Daher hält M M  auf x x  genau dann, wenn L(M)=5 |L(M')| = 5 .

Wenn L L  entscheidbar wäre, könnten wir für jedes M,x \langle M, x \rangle  die Maschine M M'  konstruieren und entscheiden, ob L(M)=5 |L(M')| = 5 , und somit das Halteproblem entscheiden. Dies ist ein Widerspruch, da H H  unentscheidbar ist. Also ist L L  unentscheidbar.

deepseek/deepseek-r1-0528

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (1.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
wrong answer for choice (0)
Beweis für Sprache 3:
Wir zeigen, dass die Sprache L={aibjck:(i1j=k)i,j,k0}L = \{ a^i b^j c^k : (i \ne 1 \vee j = k) \wedge i,j,k \ge 0 \} nicht regulär ist, indem wir die Abschlusseigenschaften regulärer Sprachen nutzen. Betrachten wir die Sprache L={wΣ:w hat die Form aibjck mit i=1}L' = \{ w \in \Sigma^* : w \text{ hat die Form } a^i b^j c^k \text{ mit } i=1 \}. Da LL' regulär ist (erkennbar durch einen endlichen Automaten, der prüft, dass das erste Zeichen aa ist und kein weiteres aa folgt, gefolgt von beliebig vielen bb und dann cc), müssen wir den Schnitt LLL \cap L' bilden:
LL={abjck:j=k}={abjcj:j0}.
L \cap L' = \{ a b^j c^k : j = k \} = \{ a b^j c^j : j \ge 0 \}.

Die Sprache {abjcj:j0}\{ a b^j c^j : j \ge 0 \} ist nicht regulär, da sie das Pumping-Lemma für reguläre Sprachen verletzt (analog zur Sprache {bjcj}\{ b^j c^j \}). Wenn LL regulär wäre, dann müsste auch LLL \cap L' regulär sein, weil reguläre Sprachen unter Schnitt abgeschlossen sind. Da jedoch LLL \cap L' nicht regulär ist, ist LL nicht regulär.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: ab
2: -
3: ba

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Die Sprache L1={wΣ:L(Mw)2=25}={wΣ:L(Mw)=5}L_1 = \{w \in \Sigma^* : |L(M_w)|^2 = 25\} = \{w \in \Sigma^* : |L(M_w)| = 5\} ist unentscheidbar. Wir beweisen dies durch Reduktion des spezifischen Halteproblems 
H={M,w:M ha¨lt und akzeptiert w} H = \{\langle M, w \rangle : M \text{ hält und akzeptiert } w\} 
auf L1L_1. Seien v1,v2,v3,v4,v5v_1, v_2, v_3, v_4, v_5 fünf verschiedene Wörter über Σ={0,1}\Sigma = \{0,1\} (z.B. ε,0,1,00,01\varepsilon, 0, 1, 00, 01). Konstruiere für eine gegebene TM MM und ein Wort ww eine TM NM,wN_{M,w}:

NM,wN_{M,w} bei Eingabe xx:
1. Falls x{v1,v2,v3,v4,v5}x \notin \{v_1, v_2, v_3, v_4, v_5\}, verwerfe.
2. Falls x=vix = v_i für ein i{1,2,3,4,5}i \in \{1, 2, 3, 4, 5\}: simuliere MM auf Eingabe ww.  
   - Akzeptiere, falls MM ww akzeptiert; andernfalls verwerfe.

Es gilt:
- Akzeptiert MM die Eingabe ww, werden alle viv_i akzeptiert: L(NM,w)=5|L(N_{M,w})| = 5.
- Akzeptiert MM ww nicht (Ablehnung oder Endlosschleife), wird kein xx akzeptiert: L(NM,w)=0|L(N_{M,w})| = 0.

Also: M,wH\langle M, w \rangle \in H gdw. NM,wL1\langle N_{M,w} \rangle \in L_1. Da HH unentscheidbar ist, ist L1L_1 unentscheidbar.

google/gemini-2.5-pro

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:
Wir beweisen, dass die Sprache L3={aibjck:(i1j=k)i,j,k0}L_3 = \{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\} nicht regulär ist.
Hierfür zeigen wir, dass der Schnitt von L3L_3 mit einer regulären Sprache eine bekannte nicht-reguläre Sprache ergibt. Da reguläre Sprachen unter dem Schnitt abgeschlossen sind, beweist dies, dass L3L_3 nicht regulär sein kann.

Sei RR die reguläre Sprache, die durch den regulären Ausdruck abcab^*c^* beschrieben wird. Also R={a1bjckj,k0}R = \{a^1b^jc^k \mid j, k \ge 0\}.
Wir betrachten die Sprache L=L3RL' = L_3 \cap R. Wenn L3L_3 regulär wäre, müsste auch LL' regulär sein.

Ein Wort w=aibjckw=a^ib^jc^k liegt in LL', wenn es sowohl in L3L_3 als auch in RR liegt.
Die Zugehörigkeit zu RR erfordert i=1i=1.
Setzen wir i=1i=1 in die Bedingung für L3L_3, (i1j=k)(i\ne 1\vee j=k), ein, erhalten wir (11j=k)(1\ne 1\vee j=k), was zu (falschj=k)(\text{falsch} \vee j=k) und somit zu j=kj=k vereinfacht wird.
Ein Wort liegt also in LL', wenn es die Form a1bjcka^1b^jc^k mit j=kj=k hat.
Somit ist L={abjcjj0}L' = \{ab^jc^j \mid j \ge 0\}.

Wir beweisen nun mit dem Pumping-Lemma, dass LL' nicht regulär ist.
Angenommen, LL' ist regulär. Dann gibt es eine Pumping-Länge p1p \ge 1.
Wir wählen das Wort s=abpcps = ab^pc^p. Offensichtlich gilt sLs \in L' und s=1+2pp|s| = 1+2p \ge p.
Gemäß dem Pumping-Lemma existiert eine Zerlegung s=xyzs=xyz mit den Eigenschaften:
1. xyp|xy| \le p
2. y1|y| \ge 1
3. xykzLxy^k z \in L' für alle k0k \ge 0.

Wegen xyp|xy| \le p und der Gestalt von s=abpcps = ab^p c^p, muss die Teilzeichenkette yy innerhalb des Präfixes abp1ab^{p-1} liegen (für p2p \ge 2; für p=1p=1 ist s=abcs=abc und xy1|xy| \le 1, also y=ay=a).
Wir analysieren die möglichen Inhalte von yy:

*   Fall 1: yy enthält das Zeichen 'a'.
    Wenn yy das 'a' enthält (z.B. y=ay=a oder y=abmy=ab^m), dann enthält das Wort xy0z=xzxy^0z = xz kein 'a' mehr, oder das Wort xy2zxy^2z enthält eine ungültige Zeichenreihenfolge wie 'ba' oder mehrere 'a's. In jedem Fall ist das Ergebnis nicht von der Form abjcjab^jc^j und liegt somit nicht in LL'. Dies widerspricht Eigenschaft 3 des Pumping-Lemmas.

*   Fall 2: yy besteht nur aus 'b's.
    Dies ist die einzig verbleibende Möglichkeit. Dann hat die Zerlegung die Form x=abux=ab^u, y=bvy=b^v, z=bpuvcpz=b^{p-u-v}c^p mit u0,v1u \ge 0, v \ge 1 und u+vp1u+v \le p-1.
    Wir betrachten das Wort s=xy2z=abu(bv)2bpuvcp=abp+vcps' = xy^2z = ab^u(b^v)^2b^{p-u-v}c^p = ab^{p+v}c^p.
    In ss' ist die Anzahl der 'b's gleich p+vp+v, während die Anzahl der 'c's pp beträgt. Da v1v \ge 1, ist p+vpp+v \ne p. Folglich hat ss' nicht die Form abjcjab^jc^j und ist somit nicht in LL'. Dies widerspricht ebenfalls Eigenschaft 3 des Pumping-Lemmas.

Da für jede mögliche Zerlegung von ss ein Widerspruch entsteht, kann die Annahme, dass LL' regulär ist, nicht korrekt sein.
Da L=L3RL' = L_3 \cap R nicht regulär ist und RR regulär ist, folgt daraus, dass L3L_3 nicht regulär sein kann.

Subproblem b (0.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
no answer for choice (0)
...
answer does not follow the template

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Die Sprache ist L1={wΣ:L(Mw)2=25}L_1 = \{w\in\Sigma^*:|L(M_w)|^2=25\}, was äquivalent zu L1={wΣ:L(Mw)=5}L_1 = \{w\in\Sigma^*:|L(M_w)|=5\} ist, da die Größe einer Sprache nicht-negativ ist. Wir beweisen die Unentscheidbarkeit von L1L_1 durch eine Reduktion vom Halteproblem H={M,xTuringmaschine M ha¨lt auf Eingabe x}H = \{\langle M, x\rangle \mid \text{Turingmaschine } M \text{ hält auf Eingabe } x\}. Das Halteproblem ist bekanntlich unentscheidbar.

Wir konstruieren eine berechenbare Funktion ff, die eine Instanz M,x\langle M, x\rangle des Halteproblems auf eine Instanz w=f(M,x)w' = f(\langle M, x\rangle) von L1L_1 abbildet, sodass M,xH    wL1\langle M, x\rangle \in H \iff w' \in L_1.
Die Funktion ff erzeugt aus M,x\langle M, x\rangle die Beschreibung ww' einer neuen Turingmaschine MM'. Die Maschine MM' arbeitet auf einer Eingabe yy wie folgt:

1.  MM' ignoriert zunächst ihre eigene Eingabe yy und simuliert die Turingmaschine MM auf der Eingabe xx.
2.  Fall A: Wenn die Simulation von MM auf xx terminiert (also hält), geht MM' zum nächsten Schritt über. MM' überprüft, ob ihre ursprüngliche Eingabe yy eine der fünf vordefinierten Zeichenketten {0,00,000,0000,00000}\{0, 00, 000, 0000, 00000\} ist.
    *   Wenn yy eine dieser fünf Zeichenketten ist, akzeptiert MM'.
    *   Andernfalls verwirft MM'.
3.  Fall B: Wenn die Simulation von MM auf xx nicht terminiert (in eine Endlosschleife gerät), wird MM' ebenfalls nicht terminieren. In diesem Fall wird der zweite Schritt nie erreicht.

Nun analysieren wir die Sprache L(M)L(M'):
*   Wenn M,xH\langle M, x\rangle \in H, dann hält MM auf xx. Gemäß Fall A in der Konstruktion von MM' wird MM' genau dann akzeptieren, wenn die Eingabe yy eine der fünf spezifischen Zeichenketten ist. Somit ist die Sprache von MM' in diesem Fall L(M)={0,00,000,0000,00000}L(M') = \{0, 00, 000, 0000, 00000\}. Die Größe der Sprache ist L(M)=5|L(M')| = 5. Folglich liegt die Beschreibung ww' von MM' in L1L_1.
*   Wenn M,xH\langle M, x\rangle \notin H, dann hält MM auf xx nicht. Gemäß Fall B in der Konstruktion von MM' gerät diese in eine Endlosschleife und akzeptiert keine einzige Eingabe. Die Sprache von MM' ist in diesem Fall leer: L(M)=L(M') = \emptyset. Die Größe der Sprache ist L(M)=0|L(M')| = 0. Da 050 \ne 5, liegt die Beschreibung ww' von MM' nicht in L1L_1.

Die Konstruktion von w=Mw'=\langle M' \rangle aus M,x\langle M, x \rangle ist ein algorithmischer Vorgang und somit ist die Funktion ff berechenbar.
Wir haben gezeigt, dass M,xH    f(M,x)L1\langle M, x\rangle \in H \iff f(\langle M, x\rangle) \in L_1. Dies stellt eine Many-one-Reduktion von HH auf L1L_1 dar (HmL1H \le_m L_1).
Da HH unentscheidbar ist, muss auch L1L_1 unentscheidbar sein.

openai/gpt-5

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:
Sei L := { a^i b^j c^k : (i ≠ 1 ∨ j = k), i,j,k ≥ 0 }. Wir zeigen: L ist nicht regulär.

Betrachte die reguläre Sprache R := a b^* c^*. Dann ist
L ∩ R = { a b^j c^k : (1 ≠ 1 ∨ j = k) } = { a b^j c^j : j ≥ 0 }.

Angenommen, L wäre regulär. Da die Klasse der regulären Sprachen unter Durchschnitt mit regulären Sprachen abgeschlossen ist, wäre dann auch L ∩ R regulär. Aber { a b^j c^j : j ≥ 0 } ist nicht regulär (Pumping-Lemma: Für Pumping-Länge p zerfällt s = a b^p c^p in xyz mit |xy| ≤ p+1 und |y| ≥ 1; y liegt ausschließlich in den b’s; Pumpen mit i=0 liefert a b^{p-|y|} c^p ∉ { a b^j c^j }, Widerspruch). Also kann L nicht regulär sein.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: ab
2: -
3: ba

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Sei L₁ := { w ∈ Σ^* : |L(M_w)|^2 = 25 } = { w : |L(M_w)| = 5 }.
Betrachte die Eigenschaft P einer von einer TM erkannten Sprache L: “|L| = 5”.
Diese Eigenschaft ist
- semantisch (hängt nur von L ab, nicht von der Repräsentation von M), und
- nichttrivial: Es gibt eine TM, die genau eine feste 5-elementige Sprache S akzeptiert (z.B. S = {ε,0,1,00,11}), und es gibt eine TM, deren Sprache nicht 5 Elemente hat (z.B. ∅).

Nach dem Satz von Rice ist jede nichttriviale semantische Eigenschaft rekursiv aufzählbarer Sprachen unentscheidbar. Also ist L₁ unentscheidbar.

(Analog ist Option 3 mit “|L| = 10” unentscheidbar; Option 2 ist leer, da keine Kardinalität n mit n²=50 existiert, also entscheidbar.)

openai/gpt-oss-120b

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (0.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
wrong answer for choice (0)
Beweis für Sprache 3:
Wir zeigen, dass die Sprache  

L={aibjck(i1    j=k)  i,j,k0}
L=\{a^{i}b^{j}c^{k}\mid (i\neq 1\;\vee\;j=k)\ \wedge\ i,j,k\ge 0\}


nicht regulär ist.  
Dazu benutzen wir die Abschluß‑Eigenschaften regulärer Sprachen und das bekannte Nicht‑Regularitäts­Resultat für  
K={abncnn0}.
K=\{ab^{n}c^{n}\mid n\ge 0\}.


---

### 1.  Komplement von LL

Das Komplement von LL (bezogen auf Σ\Sigma^{*}) ist  

L=ΣL={abjckjk}.
\overline{L}= \Sigma^{*}\setminus L
        = \{a\,b^{j}c^{k}\mid j\neq k\}.


Man erkenne, dass L\overline{L} bereits innerhalb der regulären Menge  

R=abc
R = a\,b^{*}c^{*}


liegt, also L=RL\overline{L}=R\cap\overline{L}.

---

### 2.  Annahme:  L\overline{L} wäre regulär

Angenommen, L\overline{L} wäre regulär.  
Da reguläre Sprachen unter Komplement und Schnitt mit regulären Sprachen abgeschlossen sind, würde dann auch

K=RL=R(ΣL)
K = R \setminus \overline{L}
    = R \cap (\Sigma^{*}\setminus\overline{L})


regulär sein.

Aber K={abncnn0}K = \{ab^{n}c^{n}\mid n\ge 0\} ist die klassische Beispiel­sprache, die nicht regulär ist (Pumping‑Lemma bzw. Myhill‑Nerode).  
Damit entsteht ein Widerspruch zur Annahme, dass L\overline{L} regulär ist.

---

### 3.  Schlussfolgerung

Der Widerspruch zeigt, dass L\overline{L} nicht regulär sein kann.  
Da die regulären Sprachen unter Komplement abgeschlossen sind, folgt daraus sofort, dass auch LL nicht regulär sein muss.

L ist nicht regula¨r
\boxed{L\ \text{ist nicht regulär}}


Damit ist Sprache 3 eine nicht‑reguläre Sprache, und wir haben den Beweis erbracht.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: bbab
2: -
3: babb

Subproblem c (0.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Wir zeigen, dass die Menge  
\[
L_1=\{w\in\{0,1\}^* \mid |L(M_w)|^2 = 25\}
      =\{w \mid |L(M_w)| = 5\}
\]
unentscheidbar ist, indem wir das bekannte **Leerheits‑Problem** für Turing‑maschinen  
\[
\text{EMP}=\{\langle M\rangle \mid L(M)=\varnothing\}
\]
auf sie reduzieren.

---

### 1.   Das Leerheits‑Problem ist unentscheidbar  
(standarder Satz, Beweis durch Reduktion vom Halte‑Problem).

### 2.   Konstruktion einer TM \(M'\) aus einer beliebigen TM \(M\)

Gegeben eine TM \(M\) (Kodierung \(w=\langle M\rangle\)).  
Wir bauen eine neue TM \(M'\) wie folgt:

*Fixierte Menge von fünf Strings*  
\[
S=\{0,1,00,01,10\}.
\]

\(M'\) arbeitet auf Eingabe \(x\):

1. Falls \(x\in S\) akzeptiere sofort.
2. Falls \(x = z\) (ein spezieller zusätzlicher String, z.B. \(z = 11\)), simuliere \(M\) auf **einem** festen Eingabewort (z.B. das leere Wort).  
   - Falls \(M\) mindestens ein Wort akzeptiert, akzeptiere \(z\).  
   - Andernfalls verwerfe \(z\).
3. Für jedes andere \(x\) verwerfe.

Damit gilt:

* Wenn \(L(M)=\varnothing\) akzeptiert \(M'\) **genau** die fünf Wörter aus \(S\).  
  \(|L(M')| = 5\).

* Wenn \(L(M)\neq\varnothing) akzeptiert \(M'\) die fünf Wörter aus \(S\) **und** zusätzlich \(z\).  
  \(|L(M')| = 6\) (oder sogar größer, falls man weitere Wörter zulassen würde – wichtig ist nur, dass die Größe ≠ 5 ist).

Die Konstruktion ist effektiv; es gibt eine totale, berechenbare Funktion  
\[
f:\{0,1\}^* \to \{0,1\}^*,\qquad f(w)=\langle M'\rangle .
\]

### 3.   Korrektheit der Reduktion

\[
w\in\text{EMP}\;\Longleftrightarrow\; |L(M_{f(w)})| = 5\;\Longleftrightarrow\; f(w)\in L_1 .
\]

Somit ist \(f\) eine many‑one‑Reduktion von EMP auf \(L_1\).

### 4.   Schluss

Da EMP unentscheidbar ist und EMP many‑one‑reduzierbar auf \(L_1\) ist, muss \(L_1\) ebenfalls unentscheidbar sein.  
Analog lässt sich derselbe Beweis für die Sprache mit \(|L(M_w)|^2 = 100\) (also \(|L(M_w)| = 10\)) führen; die Sprache mit \(|L(M_w)|^2 = 50\) ist dagegen leer und damit entscheidbar.

\[
\boxed{\text{Die unentscheidbaren Optionen sind }1\text{ und }3.}
\]

Beweis abgeschlossen.

qwen/qwen3-235b-a22b

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (0.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:
Sei L3:={aibjck:(i1j=k)i,j,k0} L_3 := \{a^i b^j c^k : (i \ne 1 \vee j = k) \land i, j, k \geq 0\} . Wir verwenden das Pumping-Lemma für reguläre Sprachen, um zu zeigen, dass L3 L_3  nicht regulär ist.

Angenommen, L3 L_3  ist regulär. Dann existiert eine Pumping-Länge p p , sodass sich jedes Wort aus L3 L_3  mit Länge p \geq p  in xyz x y z  aufteilen lässt, wobei gilt:
1. y1 |y| \geq 1 ,
2. xyp |xy| \leq p ,
3. i0:xyizL3 \forall i \geq 0: x y^i z \in L_3 .

Wähle das Wort s:=abpcp s := a b^p c^p  (schlüssig, da i=1 i = 1  und j=k=p j = k = p , also sL3 s \in L_3 ).

Da xyp |xy| \leq p  und der erste Teil des Wortes nach dem 'a' aus p p  'b's besteht, liegt y y  vollständig in den 'b's. Schreibe x=a x = a , y=bk y = b^k  mit k[1,p] k \in [1, p] , und z=bpkcp z = b^{p-k} c^p .

Pumpen wir i=0 i = 0 : 
xy0z=abpkcp x y^0 z = a b^{p-k} c^p .

Jetzt gilt i=1 i = 1  (kein Problem), aber j=pk j = p - k  und k=p k = p . Da k1 k \geq 1 , ist j=pk<p j = p - k < p , also jk j \ne k . Somit ist das gepumpte Wort nicht in L3 L_3 , was der Annahme widerspricht. Daher ist L3 L_3  nicht regulär.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: ba
2: -
3: aab

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Die Sprache L1:={wΣ:L(Mw)2=25} L_1 := \{w \in \Sigma^* : |L(M_w)|^2 = 25\}  ist äquivalent zu L(Mw)=5 |L(M_w)| = 5 , da 52=25 5^2 = 25 . Dies ist eine semantische Eigenschaft der Sprache L(Mw) L(M_w) , die nicht-trivial ist, weil:
- Es gibt Turingmaschinen M M  mit L(M)=5 |L(M)| = 5  (z.B. eine TM, die genau 5 Wörter akzeptiert).
- Es gibt Turingmaschinen M M'  mit L(M)5 |L(M')| \ne 5  (z.B. eine TM, die unendlich viele Wörter akzeptiert).

Nach dem Satz von Rice ist jede nicht-triviale Eigenschaft über rekursiv aufzählbare Sprachen unentscheidbar. Daher ist L1 L_1  unentscheidbar.

qwen/qwen3-235b-a22b-thinking-2507

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:
Sei angenommen, die Sprache L3={aibjck:(i1j=k)i,j,k0}L_3 = \{a^ib^jc^k: (i\ne 1\vee j=k)\wedge i,j,k\ge0\} ist regulär. Betrachte die reguläre Sprache R=abcR = a b^* c^*. Der Schnitt L3RL_3 \cap R besteht aus allen Strings der Form abjcka b^j c^k, wobei i=1i = 1 gilt. Die Bedingung (i1j=k)(i \neq 1 \vee j = k) vereinfacht sich für i=1i = 1 zu j=kj = k. Somit ist L3R={abjcjj0}L_3 \cap R = \{a b^j c^j \mid j \geq 0\}. Diese Sprache ist nicht regulär, da {bjcjj0}\{b^j c^j \mid j \geq 0\} mit dem Pumping-Lemma als nicht regulär nachweisbar ist (z.B. Wähle s=bpcps = b^p c^p; jede Zerlegung s=xyzs = xyz mit xyp|xy| \leq p führt bei Pumpen zu einem String außerhalb der Sprache). Da reguläre Sprachen unter Schnitt abgeschlossen sind, muss L3RL_3 \cap R regulär sein, wenn L3L_3 regulär wäre. Dies ist ein Widerspruch. Folglich ist L3L_3 nicht regulär.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: ab
2: -
3: aaab

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Angenommen, die Sprache L1={wΣ:L(Mw)2=25}L_1 = \{w \in \Sigma^* : |L(M_w)|^2 = 25\} ist entscheidbar. Dies ist äquivalent zu L(Mw)=5|L(M_w)| = 5, da L(Mw)|L(M_w)| eine nichtnegative ganze Zahl oder unendlich ist und 52=255^2 = 25. Die Bedingung L(Mw)=5|L(M_w)| = 5 definiert eine nichttriviale semantische Eigenschaft der Sprachen: Es gibt Turingmaschinen, deren Sprachen genau 5 Wörter enthalten (z.B. MM mit L(M)={ϵ,0,1,00,01}L(M) = \{\epsilon, 0, 1, 00, 01\}), und andere, die diese Eigenschaft nicht erfüllen (z.B. eine Maschine mit leerer Sprache). Nach dem Satz von Rice ist jede nichttriviale semantische Eigenschaft unentscheidbar. Somit ist L1L_1 unentscheidbar.

x-ai/grok-4

Exercise 8: Bonus

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P)

Sei Σ:={a,b,c}\Sigma := \{a,b,c\}. Welche der folgenden Sprachen sind NICHT regulär? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass diese nicht regulär ist.
{wΣ:wabawa}\{w\in\Sigma^*:|w|_{aba}\ne|w|_{a}\}({wΣ:w=wR})\big(\{w\in\Sigma^*:w=w^R\}\big)^*{aibjck:(i1j=k)i,j,k0}\{a^ib^jc^k:(i\ne 1\vee j=k)\wedge i,j,k\ge0\}
Beweis für Sprache 3:
Um zu zeigen, dass die Sprache nicht regulär ist, verwenden wir das Myhill-Nerode-Kriterium.

Betrachten wir die Präfixe wj=abjw_j = ab^j für j1j \geq 1.

Wir zeigen, dass für jkj \neq k mit j<kj < k die Präfixe wjw_j und wkw_k in verschiedenen Äquivalenzklassen liegen.

Sei z=cjz = c^j.

Dann ist wjz=abjcjLw_j z = ab^j c^j \in L, da hier i=1i=1, j=jj=j und somit j=kj=k gilt, also die Bedingung (i1j=k)(i \neq 1 \lor j=k) erfüllt ist.

Dagegen ist wkz=abkcjLw_k z = ab^k c^j \notin L, da i=1i=1, k>jk > j also kjk \neq j, und somit (i1k=j)(i \neq 1 \lor k=j) falsch ist.

Folglich sind wjw_j und wkw_k durch zz unterscheidbar und liegen in verschiedenen Klassen.

Da es unendlich viele solche jj gibt, hat LL unendlich viele Myhill-Nerode-Klassen und ist daher nicht regulär.

Subproblem b (1.0/1.0P)

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LL gilt LLRL\ne L^R ? Geben Sie außerdem für jede Sprache LL, die Sie gewählt haben, ein Wort ww an, das in genau einer der Sprachen L,LRL,L^R enthalten ist.

Hinweis: Um das Feld leerzulassen, geben Sie - an.
L(bab)L(b^*a^*b){wΣ:wwR}\{w\in\Sigma^*:w\ne w^R\}{uavv:u,vΣ}\{uavv:u,v\in\Sigma^*\}
1: abab
2: -
3: aabaab

Subproblem c (2.0/2.0P)

Welche der folgenden Sprachen über Σ:={0,1}\Sigma:=\{0,1\} sind unentscheidbar? Kreuzen Sie alle zutreffenden an. Wählen Sie anschließend eine solche Sprache und beweisen Sie, dass sie unentscheidbar ist.
{wΣ:L(Mw)2=25}\{w\in\Sigma^*:|L(M_w)|^2=25\}{wΣ:L(Mw)2=50}\{w\in\Sigma^*:|L(M_w)|^2=50\}{wΣ:L(Mw)2=100}\{w\in\Sigma^*:|L(M_w)|^2=100\}
Beweis für Sprache 1:
Angenommen, die Menge {wΣ:L(Mw)2=25}\{w \in \Sigma^* : |L(M_w)|^{2} = 25\} wäre entscheidbar. Das bedeutet, es gibt eine Turingmaschine DD, die für eine gegebene Kodierung M=w\langle M \rangle = w entscheidet, ob L(M)=5|L(M)| = 5 (da 52=255^2 = 25 und unendliche Kardinalitäten nicht zu 25 quadriert werden).

Wir reduzieren das Leerheitsproblem, das unentscheidbar ist, darauf.

Gegeben eine TM MM (Kodierung M\langle M \rangle), konstruieren wir MM' wie folgt:

Auf Eingabe yy:
- Wenn y=1ky = 1^k für k=1,2,3,4,5k=1,2,3,4,5, akzeptiere.
- Sonst, wenn yy mit 00 beginnt, sei zz das Wort ohne das erste 00; simuliere MM auf zz und akzeptiere genau dann, wenn MM zz akzeptiert.
- Andernfalls lehne ab.

Dann ist L(M)={1,11,111,1111,11111}{0zzL(M)}L(M') = \{1, 11, 111, 1111, 11111\} \cup \{0z \mid z \in L(M)\}.

Diese Vereinigung ist disjunkt, da die ersten Wörter mit 11 beginnen und die zweiten mit 00.

Folglich L(M)=5+L(M)|L(M')| = 5 + |L(M)|, falls L(M)|L(M)| endlich ist, und unendlich sonst.

Insbesondere gilt L(M)=5|L(M')| = 5 genau dann, wenn L(M)=0|L(M)| = 0, d.h. L(M)=L(M) = \emptyset.

Könnte DD auf M\langle M' \rangle angewendet werden, so könnte man das Leerheitsproblem für MM entscheiden, was unmöglich ist.

Daher ist die Sprache unentscheidbar.