anthropic/claude-opus-4.1

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
Begründung für i=2i=2:
(L2)∗(L_2)^* ist nicht regulär. Dies kann mit dem Pumping-Lemma gezeigt werden: Angenommen (L2)∗(L_2)^* wäre regulär mit Pumping-Länge pp. Betrachte w=apbpapbp∈(L2)∗w = a^pb^pa^pb^p \in (L_2)^* (Konkatenation zweier Strings aus L2L_2). Nach dem Pumping-Lemma gibt es eine Zerlegung w=xyzw = xyz mit ∣xy∣≤p|xy| \leq p und ∣y∣>0|y| > 0. Da ∣xy∣≤p|xy| \leq p, besteht yy nur aus aa's des ersten Blocks, also y=aky = a^k für k>0k > 0. Dann ist xy0z=ap−kbpapbpxy^0z = a^{p-k}b^pa^pb^p. Dieser String kann nicht als Konkatenation von Strings aus L2L_2 dargestellt werden, da die erste Gruppe weniger aa's als bb's hat und die verbleibenden bb's nicht mit den folgenden aa's zu einem balancierten String kombiniert werden können. Widerspruch!

Subproblem b (0.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: 
wrong answer for choice (0)
In CNF benötigt man für einen String der Länge nn genau n−1n-1 Anwendungen binärer Regeln. Für a9a^9 brauchen wir 8 binäre Regelanwendungen, für a12a^{12} brauchen wir 11. Die Ableitungsbäume müssen sich strukturell unterscheiden, um diese verschiedenen Längen zu erreichen. Mit nur 6 Produktionen können wir nicht genügend verschiedene Ableitungspfade konstruieren, um genau diese beiden spezifischen Längen zu erzeugen, da wir mehrere Nicht-Terminale mit ihren jeweiligen Produktionen benötigen würden.
0: could not parse value In CNF benötigt man für einen String der Länge n genau n-1 Anwendungen binärer Regeln. Für a^9 brauchen wir 8 binäre Regelanwendungen, für a^{12} brauchen wir 11. Die Ableitungsbäume müssen sich strukturell unterscheiden, um diese verschiedenen Längen zu erreichen. Mit nur 6 Produktionen können wir nicht genügend verschiedene Ableitungspfade konstruieren, um genau diese beiden spezifischen Längen zu erzeugen, da wir mehrere Nicht-Terminale mit ihren jeweiligen Produktionen benötigen würden. 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 L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 1:
Da LL kontextfrei aber nicht regulär ist, muss LL unendlich sein (jede endliche Sprache ist regulär). Eine unendliche Menge hat überabzählbar viele Teilmengen. Es gibt aber nur abzählbar viele entscheidbare Sprachen, da es nur abzählbar viele Turingmaschinen gibt. Nach dem Schubfachprinzip muss es daher überabzählbar viele unentscheidbare Teilmengen von LL geben. Insbesondere existiert mindestens eine unentscheidbare Sprache L′⊆LL' \subseteq L.

anthropic/claude-sonnet-4

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
Begründung für i=2i=2:
(L2)∗(L_2)^* ist nicht regulär. Beweis mit Pumping-Lemma: Sei pp die Pumping-Länge und betrachte w=(apbp)p∈(L2)∗w = (a^pb^p)^p \in (L_2)^*. Da ∣xy∣≤p|xy| \leq p liegt xyxy vollständig im ersten apa^p-Teil, also x=aj,y=akx = a^j, y = a^k mit k≥1k \geq 1. Beim Herunterpumpen (i=0i=0) erhalten wir xzxz mit erstem Block ap−kbpa^{p-k}b^p. Für (L2)∗(L_2)^*-Zugehörigkeit müsste p−k=pp-k = p gelten, also k=0k = 0, Widerspruch zu k≥1k \geq 1.

Subproblem b (0.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: 
wrong answer for choice (0)
For any string ana^n in CNF, we need approximately n−1n-1 binary productions to create the tree structure, plus terminal productions. Even with optimal sharing between the derivations for a9a^9 and a12a^{12}, we need separate substructures for different factors. The minimal constructions I attempted all required 7-8 productions, suggesting that 6 productions are insufficient to generate both strings while maintaining the precise language L(G)={a12,a9}L(G) = \{a^{12}, a^9\}.
0: could not parse value For any string a^n in CNF, we need approximately n-1 binary productions to create the tree structure, plus terminal productions. Even with optimal sharing between the derivations for a^9 and a^{12}, we need separate substructures for different factors. The minimal constructions I attempted all required 7-8 productions, suggesting that 6 productions are insufficient to generate both strings while maintaining the precise language 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 L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 1:
Da LL kontextfrei und nicht regulär ist, ist LL unendlich und entscheidbar. Wir können die Elemente von LL als w1,w2,w3,…w_1, w_2, w_3, \ldots aufzählen. Sei HH das Halteproblem. Definiere L′={wi:i∈H}L' = \{w_i : i \in H\}. Dann ist L′⊆LL' \subseteq L, aber L′L' ist unentscheidbar, da die Entscheidung ob wi∈L′w_i \in L' äquivalent zur Entscheidung ob i∈Hi \in H ist, was unentscheidbar ist.

deepseek/deepseek-chat-v3.1

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
Begründung für i=2:
Wenn (L₂)* regulär wäre, dann wäre der Schnitt mit der regulären Sprache a*b* auch regulär. jedoch ist (L₂)* ∩ a*b* = L₂, und L₂ ist nicht regulär (da es die Sprache {a^n b^n | n ∈ ℕ} ist, die nicht regulär ist). Daher kann (L₂)* nicht regulär sein.

Subproblem b (1.0/1.0P) 

Gibt es eine kontextfreie Grammatik GG in Chomsky-Normalform mit höchstens 66 Produktionen und L(G)={a12,a9}L(G)=\{a^{12},a^9\}? Falls ja, geben Sie eine solche Grammatik an, falls nein, begründen Sie dies kurz.
☒Ja, Grammatik:☐Nein, Begründung: 
S → C D | D D  
C → A B  
B → A A  
A → a  
D → C C

Subproblem c (2.0/2.0P) 

Sei L⊆{0,1}∗L\subseteq\{0,1\}^* eine beliebige kontextfreie und nicht reguläre Sprache. Welche der folgenden Aussagen sind wahr? (Es können mehrere sein.) Wählen Sie eine solche Aussage und begründen Sie kurz, wieso diese Aussage wahr ist.
☒Es gibt eine unentscheidbare Sprache L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 1:
Da L kontextfrei und nicht regulär ist, muss L unendlich sein (alle endlichen Sprachen sind regulär). Unendliche Sprachen haben überabzählbar viele Teilmengen, aber es gibt nur abzählbar viele entscheidbare Sprachen. Daher muss es unentscheidbare Teilmengen L' ⊆ L geben.

deepseek/deepseek-r1-0528

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
Begründung für i=2i=2:
Angenommen, (L2)∗(L_2)^* 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 ∣xy∣≤p|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 1≤k≤p1 \leq k \leq p. Dann ist xy0z=ap−kbp(apbp)p−1xy^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 ap−kbpa^{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 ap−kbpa^{p-k} b^p mit p−k<pp-k < p bleibt nach einem möglichen Block ambma^m b^m (mit m≤p−km \leq p-k) ein Suffix bp−mapb^{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 L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 1:
Da LL kontextfrei und nicht regulär ist, muss LL unendlich sein (denn alle endlichen Sprachen sind regulär). Für jede unendliche Sprache LL existiert eine unentscheidbare Teilmenge L′⊆LL' \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 L′⊆LL' \subseteq L.

google/gemini-2.5-pro

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
Begründung für i=2i=2:
Wir beweisen mittels des Pumping-Lemmas für reguläre Sprachen, dass (L2)∗(L_2)^* nicht regulär ist.
Sei L:=(L2)∗=({anbn:n∈N})∗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 w∈L2w \in L_2 und per Definition L2⊆LL_2 \subseteq L, ist auch w∈Lw \in L.
Weiterhin gilt ∣w∣=2p≥p|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. ∣xy∣≤p|xy| \le p
2. ∣y∣≥1|y| \ge 1
3. Für alle i≥0i \ge 0 gilt xyiz∈Lxy^iz \in L.

Aufgrund der Bedingung ∣xy∣≤p|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 k≥1k \ge 1 (wegen ∣y∣≥1|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 ap−kbpa^{p-k}b^p.
Laut Pumping-Lemma muss w′∈Lw' \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 n≥1n \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,n2≥1n_1, n_2 \ge 1) enthält zwingend den Teilstring "ba".
Das Wort w′=ap−kbpw' = a^{p-k}b^p enthält jedoch kein "ba". Damit w′w' in LL liegen kann, muss es entweder das leere Wort sein (was nicht der Fall ist, da p≥1p \ge 1) oder selbst ein Element von L2L_2 sein.

Damit w′=ap−kbpw' = 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 p−k=pp-k = p gelten. Dies impliziert k=0k=0.
Dies steht jedoch im Widerspruch zur Bedingung ∣y∣=k≥1|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:
S→A8A4S \to A_8 A_4
S→A8AS \to A_8 A
A8→A4A4A_8 \to A_4 A_4
A4→A2A2A_4 \to A_2 A_2
A2→AAA_2 \to A A
A→aA \to a

Diese Grammatik hat 6 Produktionen und ist in Chomsky-Normalform, da jede Regel die Form A→BCA \to BC oder A→aA \to a hat.

Herleitung der Sprache L(G)L(G):
- AA leitet das Wort a1=aa^1=a ab.
- A2→AAA_2 \to AA leitet a1a1=a2a^1a^1 = a^2 ab.
- A4→A2A2A_4 \to A_2A_2 leitet a2a2=a4a^2a^2 = a^4 ab.
- A8→A4A4A_8 \to A_4A_4 leitet a4a4=a8a^4a^4 = a^8 ab.
- Die erste Startregel S→A8A4S \to A_8A_4 leitet a8a4=a12a^8a^4 = a^{12} ab.
- Die zweite Startregel S→A8AS \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 L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\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 L′L', 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 L′⊆LL' \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 L′⊆LL' \subseteq L bewiesen.

openai/gpt-5

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
Begründung für i=2i=2:
Betrachte R:=a∗b∗R := a^*b^* regulär. Dann gilt
(L2)∗∩R={(an1bn1)⋯(ankbnk):k≥0}∩a∗b∗={anbn:n∈N}=L2(L_2)^* \cap R = \{(a^{n_1}b^{n_1})\cdots(a^{n_k}b^{n_k}) : k\ge 0\} \cap a^*b^* = \{a^n b^n : n\in\mathbb{N}\} = L_2,
denn jede Konkatenation von mindestens zwei Blöcken erzeugt ein Vorkommen von „ba“ und liegt somit nicht in a∗b∗a^*b^*. Wäre (L2)∗(L_2)^* regulär, so wäre wegen Abschluss unter Schnitt auch L2L_2 regulär — Widerspruch. Also 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: 
S -> C D
S -> D D
D -> C C
C -> A B
B -> A A
A -> a

Subproblem c (2.0/2.0P) 

Sei L⊆{0,1}∗L\subseteq\{0,1\}^* eine beliebige kontextfreie und nicht reguläre Sprache. Welche der folgenden Aussagen sind wahr? (Es können mehrere sein.) Wählen Sie eine solche Aussage und begründen Sie kurz, wieso diese Aussage wahr ist.
☒Es gibt eine unentscheidbare Sprache L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 1:
Da LL kontextfrei, nicht regulär und damit unendlich ist, hat die Potenzmenge P(L)\mathcal{P}(L) überabzählbar viele Elemente, während es nur abzählbar viele Turingmaschinen (und damit entscheidbare Sprachen) gibt. Also gibt es (sogar überabzählbar viele) unentscheidbare Teilmengen L′⊆LL'\subseteq L.

openai/gpt-oss-120b

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (0.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☒L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
wrong answer for choice (2)
Begründung für i=2i=2:
L2={anbn∣n∈N}
L_2 = \{a^n b^n \mid n\in\mathbb N\}

ist die klassische Kopiersprache, die nicht regulär ist (Pumping‑Lemma).  
Für jedes Wort w=anbn∈L2w = a^n b^n\in L_2 gilt, dass jede Zerlegung w=xyzw = xyz mit ∣xy∣≤p|xy|\le p und ∣y∣>0|y|>0 nach dem Pumpen von yy zu xykzxy^kz (für k≠1k\neq1) zu einer Ungleichheit zwischen der Anzahl der aa’s und bb’s führt, also zu einem Wort, das nicht mehr in L2L_2 liegt – ein Widerspruch zur Annahme, dass L2L_2 regulär ist.  

Da L2L_2 selbst nicht regulär ist, kann ihr Kleene‑Stern (L2)∗(L_2)^* ebenfalls nicht regulär sein:  
(L2)∗={an1bn1an2bn2…ankbnk∣k≥0,  ni≥0}
(L_2)^* = \{a^{n_1}b^{n_1}a^{n_2}b^{n_2}\dots a^{n_k}b^{n_k} \mid k\ge 0,\; n_i\ge 0\}

Enthält bereits die Teilmenge {anbn∣n≥0}\{a^n b^n\mid n\ge 0\} (für k=1k=1), die nicht regulär ist.  
Wäre (L2)∗(L_2)^* regulär, wäre auch diese Teilmenge regulär (Regulär­sprachen sind unter Schnitt mit regulären Sprachen abgeschlossen), was zum bekannten Ergebnis {anbn}\{a^n b^n\} ∉\notin REG führt – ein Widerspruch.  

Somit ist (L2)∗(L_2)^* nicht regulär.

Subproblem b (0.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: 
wrong answer for choice (0)
Eine kontextfreie Grammatik in Chomsky‑Normalform kann nur Produktionen der Form  
A→BCA \to BC oder A→aA \to a (plus eventuell S→εS\to\varepsilon ) enthalten.  
Um die beiden Wörter a9a^{9} und a12a^{12} zu erzeugen, muss die Grammatik
einen Wahlpunkt besitzen, an dem entweder ein Ableitungsbaum mit
99 Blatt‑Terminals oder ein Ableitungsbaum mit 1212 Blatt‑Terminals
entsteht.  

In Chomsky‑Normalform ist jede Ableitung durch einen binären
Ableitungsbaum gegeben, dessen Blätter exakt die erzeugten
Terminale sind. Ein Wahlpunkt in einer CNF‑Grammatik ist immer eine
Regel der Form A→BCA\to BC. Der resultierende Ableitungsbaum
enthält dann beide Teilbäume, also wird die Zeichenkette
die Konkatenation der beiden Teilbäume. Damit entstehen stets
die Gesamtlängen

(La¨nge des linken Teilbaums)+(La¨nge des rechten Teilbaums).
\text{(Länge des linken Teilbaums)} + \text{(Länge des rechten Teilbaums)} .


Damit kann keine CNF‑Grammatik nur zwei verschiedene Längen
erzeugen, ohne weitere Kombinationen zu erlauben.  
Um ausschließlich die beiden Wörter a9a^{9} bzw. a12a^{12} zu
generieren, wäre ein Produktions­regel der Form  
S→A∣BS \to A \mid B (eine Wahl zwischen zwei Nicht‑Terminals)
erforderlich; solche Einheits­produktionen sind in
Chomsky‑Normalform jedoch nicht zulässig.  

Daher gibt es keine CNF‑Grammatik mit höchstens sechs
Produktionen, die exakt die Sprache {a12,a9}\{a^{12},a^{9}\} erzeugt.

Folgerung:  
Keine solche Grammatik existiert.
0: could not parse value
    Eine kontextfreie Grammatik in Chomsky‑Normalform kann nur Produktionen der Form
    \(A \to BC\) oder \(A \to a\) (plus eventuell \(S\to\varepsilon\) ) enthalten.
    Um die beiden Wörter \(a^{9}\) und \(a^{12}\) zu erzeugen, muss die Grammatik
    einen Wahlpunkt besitzen, an dem entweder ein Ableitungsbaum mit
    \(9\) Blatt‑Terminals oder ein Ableitungsbaum mit \(12\) Blatt‑Terminals
    entsteht.
    
    In Chomsky‑Normalform ist jede Ableitung durch einen binären
    Ableitungsbaum gegeben, dessen Blätter exakt die erzeugten
    Terminale sind. Ein Wahlpunkt in einer CNF‑Grammatik ist immer eine
    Regel der Form \(A\to BC\). Der resultierende Ableitungsbaum
    enthält dann **beide** Teilbäume, also wird die Zeichenkette
    die Konkatenation der beiden Teilbäume. Damit entstehen stets
    die Gesamtlängen
    
    \[
    \text{(Länge des linken Teilbaums)} + \text{(Länge des rechten Teilbaums)} .
    \]
    
    Damit kann keine CNF‑Grammatik nur **zwei** verschiedene Längen
    erzeugen, ohne weitere Kombinationen zu erlauben.
    Um ausschließlich die beiden Wörter \(a^{9}\) bzw. \(a^{12}\) zu
    generieren, wäre ein Produktions­regel der Form
    \(S \to A \mid B\) (eine Wahl zwischen zwei Nicht‑Terminals)
    erforderlich; solche **Einheits­produktionen** sind in
    Chomsky‑Normalform jedoch nicht zulässig.
    
    Daher gibt es keine CNF‑Grammatik mit höchstens sechs
    Produktionen, die exakt die Sprache \(\{a^{12},a^{9}\}\) erzeugt.
    
    **Folgerung:**
    Keine solche Grammatik existiert.
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 L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 1 (1 oder 2):
Da LL kontextfrei und damit entscheidbar ist, besitzt sie mindestens unendlich viele Wörter (jede nicht‑reguläre CFL ist unendlich).  
Aus einer unendlichen, entscheidbaren Menge lässt sich durch eine geeignete kodierende Abbildung eine beliebige Teilmenge der natürlichen Zahlen realisieren.  

Wählt man z. B. eine effektive, injektive Abbildung  
π:N→L\pi:\mathbb N \rightarrow L (möglich, weil LL unendlich ist), so kann jede Sprache K⊆NK\subseteq\mathbb N in die Form  
L′={π(n)∣n∈K}⊆LL' = \{\pi(n) \mid n\in K\}\subseteq L überführt werden.  

Da es unentscheidbare Teilmengen von N\mathbb N gibt (z. B. die Halte‑Sprache), liefert die entsprechende Menge L′L' eine unentscheidbare Sprache, die vollständig in LL liegt.  

Damit existiert für jede nicht‑reguläre kontextfreie Sprache LL mindestens ein unentscheidbares L′⊆LL'\subseteq L.  
Die zweite Aussage ist falsche, weil bereits das obige Gegenbeispiel zeigt, dass nicht jede Teilmenge entscheidbar ist.

qwen/qwen3-235b-a22b

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
Begründung für i=2i=2:
Die Sprache L2={anbn:n∈N}L_2 = \{a^nb^n : n \in \mathbb{N}\} ist bekanntermaßen nicht regulär (Beweis z.B. mit dem Pumping-Lemma). Wir zeigen, dass (L2)∗(L_2)^* ebenfalls nicht regulär ist. Angenommen, (L2)∗(L_2)^* wäre regulär. Dann gäbe es eine Pumping-Lemma-Konstante pp. Betrachte das Wort w=apbpapbp∈(L2)∗w = a^pb^pa^pb^p \in (L_2)^*. Zerlege w=xyzw = xyz mit ∣xy∣≤p|xy| \leq p und ∣y∣≥1|y| \geq 1. Da ∣xy∣≤p|xy| \leq p, besteht yy nur aus aa's. Pumpen wir yy auf xy0zxy^0z, erhalten wir ap−kbpapbpa^{p-k}b^pa^pb^p für ein k≥1k \geq 1. Dieses Wort lässt sich nicht als Konkatenation von Wörtern aus L2L_2 darstellen, da der erste Block ap−kbpa^{p-k}b^p nicht in L2L_2 liegt (ungleiche Anzahl an aa's und bb's). Dies widerspricht dem Pumping-Lemma, also ist (L2)∗(L_2)^* nicht regulär.

Subproblem b (0.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 → XD | DD  
X → AB  
B → AA  
A → a  
D → XX  
(Alle Produktionen in CNF mit insgesamt 6 Regeln)
0: could not parse value
    S → XD | DD
    X → AB
    B → AA
    A → a
    D → XX
    (Alle Produktionen in CNF mit insgesamt 6 Regeln)
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 L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 11 (1 oder 2):
Da LL eine überabzählbare Teilmenge von {0,1}∗\{0,1\}^* ist und unendlich viele Elemente enthält, besitzt LL überabzählbar viele Teilmengen L′⊆LL' \subseteq L. Die Menge aller entscheidbaren Sprachen ist jedoch abzählbar, da Turing-Maschinen abzählbar sind. Somit muss es notwendigerweise Teilmengen L′L' von LL geben, die nicht entscheidbar sind. Dies gilt unabhängig davon, dass LL selbst kontextfrei (und damit entscheidbar) ist. Daher ist Aussage 11 wahr.

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

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (0.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☒L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
wrong answer for choice (2)
Begründung für i=2i=2:
Die Sprache (L2)∗(L_2)^* enthält alle Konkatenationen von Strings der Form anbna^n b^n. Um zu zeigen, dass (L2)∗(L_2)^* nicht regulär ist, verwenden wir das Pumping-Lemma für reguläre Sprachen. Angenommen, (L2)∗(L_2)^* wäre regulär mit Pumping-Länge pp. Betrachte das Wort s=apbps = a^p b^p, das in L2⊆(L2)∗L_2 \subseteq (L_2)^* liegt. Laut Pumping-Lemma lässt sich ss zerlegen in xyzxyz mit ∣xy∣≤p|xy| \leq p, ∣y∣≥1|y| \geq 1, sodass xyiz∈(L2)∗xy^iz \in (L_2)^* für alle i≥0i \geq 0. Da yy nur aus aa's besteht (wegen ∣xy∣≤p|xy| \leq p), führt das Pumpen (z. B. i=0i = 0) zu einem Wort xz=ap−∣y∣bpxz = a^{p - |y|} b^p mit ungleicher Anzahl von aa's und bb's. Dieses Wort kann jedoch nicht als Konkatenation von akbka^k b^k-Blöcken dargestellt werden, da die Gesamtzahl der aa's ungleich der bb's ist (und jede Konkatenation solcher Blöcke eine gleiche Gesamtzahl erfordert). Dies widerspricht dem Pumping-Lemma, also 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: 
S→XZ∣ZZS \to XZ \mid ZZ
X→AYX \to AY
Y→AAY \to AA
Z→XXZ \to XX
A→aA \to a

Subproblem c (2.0/2.0P) 

Sei L⊆{0,1}∗L\subseteq\{0,1\}^* eine beliebige kontextfreie und nicht reguläre Sprache. Welche der folgenden Aussagen sind wahr? (Es können mehrere sein.) Wählen Sie eine solche Aussage und begründen Sie kurz, wieso diese Aussage wahr ist.
☒Es gibt eine unentscheidbare Sprache L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 11:
Da LL kontextfrei und nicht regulär ist, muss LL unendlich sein (alle endlichen Sprachen sind regulär). Eine unendliche Sprache L⊆{0,1}∗L \subseteq \{0,1\}^* hat überabzählbar viele Teilmengen. Da es jedoch nur abzählbar viele entscheidbare Sprachen gibt (jede entscheidbare Sprache entspricht einer Turingmaschine, und Turingmaschinen sind abzählbar), muss es Teilmengen L′⊆LL' \subseteq L geben, die nicht entscheidbar sind. Insbesondere existiert daher stets eine unentscheidbare Teilmenge L′L', was Aussage 11 wahr macht.

x-ai/grok-4

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (2.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☐L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
Begründung für i=2i=2:
Angenommen (L2)∗(L_2)^* wäre regulär mit Pumplänge pp. Betrachte w=apbpapbp∈(L2)∗w = a^p b^p a^p b^p \in (L_2)^*. Dann liegt jede Zerlegung xyzxyz mit ∣xy∣≤p|xy| \le p, ∣y∣≥1|y| \ge 1 in den ersten apa^p. Für k=0k=0 ist xz=ap−tbpapbp∉(L2)∗xz = a^{p-t} b^p a^p b^p \notin (L_2)^*, da es nicht in aufeinanderfolgende Blöcke akbka^k b^k zerlegt werden kann (nach dem ersten möglichen Block ap−tbp−ta^{p-t} b^{p-t} bleibt btapbpb^t a^p b^p übrig, das mit bb beginnt, was kein Block kann). Widerspruch zum Pumplemma.

Subproblem b (1.0/1.0P) 

Gibt es eine kontextfreie Grammatik GG in Chomsky-Normalform mit höchstens 66 Produktionen und L(G)={a12,a9}L(G)=\{a^{12},a^9\}? Falls ja, geben Sie eine solche Grammatik an, falls nein, begründen Sie dies kurz.
☒Ja, Grammatik:☐Nein, Begründung: 
S -> C D | D D
D -> C C
C -> A B
B -> A A
A -> a

Subproblem c (2.0/2.0P) 

Sei L⊆{0,1}∗L\subseteq\{0,1\}^* eine beliebige kontextfreie und nicht reguläre Sprache. Welche der folgenden Aussagen sind wahr? (Es können mehrere sein.) Wählen Sie eine solche Aussage und begründen Sie kurz, wieso diese Aussage wahr ist.
☒Es gibt eine unentscheidbare Sprache L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 1:
Da LL kontextfrei und nicht regulär ist, ist LL unendlich (denn endliche Sprachen sind regulär). Da LL entscheidbar ist, lässt sich eine effektive Aufzählung e1,e2,…e_1,e_2,\dots aller Wörter in LL berechnen. Sei K={n∈N∣K=\{n\in\mathbb{N}\mid die nn-te TM hält auf leerem Band}\}. Definiere L′={en∣n∈K}L'=\{e_n\mid n\in K\}. Dann ist L′⊆LL'\subseteq L unentscheidbar, da sich das Halteproblem auf L′L' reduzieren lässt.

z-ai/glm-4.5

Exercise 8: Bonus

Die Punkte dieser Aufgabe sind Bonuspunkte, d.h. sie zählen wie normale Punkte, werden bei der Berechnung des Notenschemas jedoch außer Acht gelassen.

Mindestens eine Antwortmöglichkeit ist immer richtig.

Subproblem a (0.0/2.0P) 

Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.
☐L1:={(ab)n:n∈N}L_1 := \{(ab)^n:n\in\mathbb{N}\}☒L2:={anbn:n∈N}L_2 := \{a^nb^n:n\in\mathbb{N}\}☒L3:={anbm:n,m∈N∧n≠m}L_3 := \{a^nb^m:n,m\in\mathbb{N}\wedge n\ne m\} 
wrong answer for choice (2)
Begründung für i=2i=2:
Angenommen, (L2)∗(L_2)^* ist regulär. Dann existiert eine Pumping-Länge pp gemäß dem Pumping-Lemma für reguläre Sprachen.

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

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

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

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

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

Subproblem b (1.0/1.0P) 

Gibt es eine kontextfreie Grammatik GG in Chomsky-Normalform mit höchstens 66 Produktionen und L(G)={a12,a9}L(G)=\{a^{12},a^9\}? Falls ja, geben Sie eine solche Grammatik an, falls nein, begründen Sie dies kurz.
☒Ja, Grammatik:☐Nein, Begründung: 
A1→aA_1 \to a
A2→A1A1A_2 \to A_1A_1
A4→A2A2A_4 \to A_2A_2
A8→A4A4A_8 \to A_4A_4
S→A8A1S \to A_8A_1
S→A8A4S \to A_8A_4

Subproblem c (2.0/2.0P) 

Sei L⊆{0,1}∗L\subseteq\{0,1\}^* eine beliebige kontextfreie und nicht reguläre Sprache. Welche der folgenden Aussagen sind wahr? (Es können mehrere sein.) Wählen Sie eine solche Aussage und begründen Sie kurz, wieso diese Aussage wahr ist.
☒Es gibt eine unentscheidbare Sprache L′⊆LL'\subseteq L.☐Jede Sprache L′⊆LL'\subseteq L ist entscheidbar. 
Begründung für Aussage 1:
Da LL kontextfrei ist, ist LL entscheidbar. Zudem ist LL nicht regulär, weshalb LL unendlich sein muss (da alle endlichen Sprachen regulär sind). Jede unendliche entscheidbare Sprache enthält unentscheidbare Teilmengen. Dies folgt aus Kardinalitätsargumenten: Die Potenzmenge einer unendlichen Menge ist überabzählbar, während die Menge der entscheidbaren Sprachen abzählbar ist (da es nur abzählbar viele Turingmaschinen gibt). Daher muss es Sprachen L′⊆LL' \subseteq L geben, die nicht entscheidbar sind.