Exam 2024_endterm.txt — openai/gpt-oss-120b

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 0.0/3.0 9.0/12.0
5: Kontextfreie Sprachen 0.0/6.0 4.0/4.0 3.0/3.0 7.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 0.0/2.0 0.0/1.0 2.0/2.0 2.0/5.0
Exam total 92.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 L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' 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?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{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...xk∈L∧x1,...,xk∈Σ∧k≥0}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}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(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:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,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\}.

r_1=((a|b)(a|b))*
r_2=(b|ab)*
r_3=((ab)*b(ab)*b)*(ab)*

Subproblem g (3.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', 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, DFA☐Falsch, Begründung 
DFA M′

- Zustände: 0, 1, 2  
- Eingabealphabet: {a,b}  
- Startzustand: 2  
- Endzustände: {2}  
- Übergangsfunktion (wie bei M)

ab012102202
\begin{array}{c|cc}
   & a & b \\ \hline
0 & 1 & 2 \\
1 & 0 & 2 \\
2 & 0 & 2
\end{array}


Der Übergangsgraph ist identisch zu dem von M; nur der Startzustand ist 2 statt 0.  
Damit ist  

L(M′)={ w∣nach w befindet sich der Automat in Zustand 2}
L(M') = \{\,w \mid \text{nach }w \text{ befindet sich der Automat in Zustand }2\} 


die rechte Sprache von Zustand 2, also ein anderer regulärer Sprachteil als L(M)L(M) (z.\,B. ε∈L(M′)\varepsilon \in L(M') aber ε∉L(M)\varepsilon \notin L(M)).  

Da die Menge der rechten Sprachen (Residualsprachen) aller Zustände unverändert bleibt, gilt  

{ L(M)w:w∈Σ∗ }={ L(M′)w:w∈Σ∗ },
\{\,L(M)^w : w\in\Sigma^*\,\}= \{\,L(M')^w : w\in\Sigma^*\,\},


wobei gleichzeitig L(M)≠L(M′)L(M)\neq L(M').  Hence such a DFA exists.

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:={q∈Q:[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\}$

Erklärung:<br>
Aus der Äquivalenztabelle sehen wir, dass nur die Paare **(0,1)** und **(3,4)** mit „$=$“ markiert sind, also jeweils äquivalente Zustände besitzen. Alle anderen Paare erhalten ein unterscheidendes Wort (z. B. „$a$“, „$ba$“ oder „$\varepsilon$“), was bedeutet, dass diese Zustände **nicht** äquivalent sind. Damit ergeben sich die folgenden Äquivalenzklassen:

- $\{0,1\}$ (wegen (0,1) =)<br>
- $\{3,4\}$ (wegen (3,4) =)<br>
- $\{2\}$ (kein anderes $q$ ist zu 2 gleich)<br>
- $\{5\}$ (kein anderes $q$ ist zu 5 gleich)

Die Zustände, deren Äquivalenzklasse nur aus sich selbst besteht, sind also $2$ und $5$, was exakt die Menge $S$ liefert.






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\}, \{3,4\}, \{2\}, \{5\}  
Startzustand: \{0,1\}  
Finalzustände: \{5\}  
Transitionen:
{0,1}, a -> {3,4} 
{0,1}, b -> {2}
{3,4}, a -> {0,1} 
{3,4}, b -> {3,4}
{2}, a -> {5} 
{2}, b -> {3,4}
{5}, a -> {5} 
{5}, b -> {3,4}






Subproblem d (2.0/2.0P) 






Wir betrachten den folgenden DFA M′M':
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 M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.



0: ε\varepsilon  
1: abab  
2: bb  
3: ε\varepsilon  
4: baabaa  
5: aaaa  
6: aa  
7: ε\varepsilon






Subproblem e (3.0/3.0P) 






Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.



Lanbnc={ b na n }L^{a^nb^nc}=\{\,b^{\,n}a^{\,n}\,\}  
Lcban=∅L^{cba^n}=\emptyset  
Lan={ v c vR a n∣v∈{a,b}∗ }L^{a^n}=\{\,v\,c\,v^{R}\,a^{\,n}\mid v\in\{a,b\}^{*}\,\}






Subproblem f (3.0/4.0P) 






Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\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:=a nw_n := a^{\,n}  

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N, i≠ji,j\in\mathbb{N},\,i\ne j:

Für ein festes k∈Nk\in\mathbb{N} betrachten wir das Residuum nach dem Präfix aka^{k}:
Lak={ x∈{a,b}∗∣akx∈L }.
L^{a^{k}}=\{\,x\in\{a,b\}^* \mid a^{k}x\in L\,\}.


Da jedes Wort in LL genau aus einer Block von aa’s gefolgt von einem Block von bb’s besteht, ist jedes zulässiges Folgewort xx zwingend von der Form bmb^{m} (ein weiteres aa würde die Struktur von LL zerstören).  
Weiter gilt:

akbm∈L  Longleftrightarrow  k≠m.
a^{k}b^{m}\in L 
\iff k\neq m .


Damit

Lak={ bm∣m∈N, m≠k }.(1)
L^{a^{k}} = \{\,b^{m}\mid m\in\mathbb{N},\ m\neq k\,\}.
\tag{1}


Nun sei i≠ji\neq j. Ohne Beschränkung der Allgemeinheit sei i<ji<j.  
Betrachte das Wort bib^{i}.

* Nach (1) ist bi∉Laib^{i}\notin L^{a^{i}}, weil dort genau das Wort bib^{i} fehlt (es erfüllt m=im=i).
* Ebenfalls nach (1) ist bi∈Lajb^{i}\in L^{a^{j}}, weil i≠ji\neq j und damit bib^{i} nicht das verbotene Wort bjb^{j} ist.

Somit enthält LajL^{a^{j}} das Wort bib^{i}, während LaiL^{a^{i}} dieses Wort nicht enthält. Also
Lai≠Laj.
L^{a^{i}}\neq L^{a^{j}}.


Da dies für jedes unterschiedliche Paar i,ji,j gilt, gibt es unendlich viele paarweise verschiedene Residualsprachen von LL. Nach dem Myhill‑Nerode‑Theorem ist LL deshalb nicht regulär. ∎








Exercise 3: NFA-Konstruktion


Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet L↓0L^{\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:
L↓0:={uvw:u0v0w∈L∧u,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:=(0∣1)(0∣1)r_1:=(0\mid 1)(0\mid 1), s1=εs_1=\varepsilon  
r2:=(0∣1)∗r_2:=(0\mid 1)^*, s2=(0∣1)∗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 Q′Q', q0′q_0', F′F', 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′,p′∈Q′,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



**Allgemeine Konstruktion**

**Zustände**  
\(Q' = Q \times \{0,1,2\}\) (der zweite Faktor zählt, wie viele Nullen bereits gelöscht wurden)

**Startzustand**  
\(q_0' = (q_0,0)\)

**Endzustände**  
\(F' = \{ (q,2) \mid q\in F\}\) (der originale Endzustand *nach* exakt zwei gelöschten Nullen)

**Übergangs‑Funktion**  

Für jedes \(k\in\{0,1,2\}\) und jedes \(a\in\Sigma\) definiere  

\[
\begin{aligned}
&\text{(a) normale Übergänge:}&
\delta'((q,k),a) &:= \{\, (p,k) \mid p\in\delta(q,a) \,\}  \\[2mm]
&\text{(b) „Überspring‑Übergänge“ (nur bei 0 und wenn noch nicht 2 Nullen gelöscht wurden):}\\
\delta'((q,k),0) &:= \{ (k+1) \text{-Zustand} \mid k<2\}\\
&\text{d.h. } \delta'((q,k),0) \supseteq \{\, (q,k+1) \,\}\;\text{für }k=0,1
\end{aligned}
\]

Kurz gesagt:  
* Alle ursprünglichen Übergänge bleiben unverändert (der Zähler ändert sich nicht).  
* Zusätzlich darf aus jedem Zustand bei Eingabe ‘0’ ein **Zusatz‑Übergang** gewählt werden, der das aktuelle Symbol **verbraucht**, aber den Zustand nicht ändert und den Zähler um 1 erhöht.  

---

### Anwendung auf den NFA \(M_1\)

**Ursprünglicher NFA \(M_1\)**  

Zustände: \(q_1,q_2,q_3\)  
Start: \(q_1\)  Ende: \(q_3\)  

Übergänge  

\[
\begin{array}{c|c}
\text{Quelle} & \text{Eingabe} \rightarrow \text{Ziel} \\ \hline
q_1 & 0 \rightarrow q_2 \\[1mm]
q_2 & 1 \rightarrow q_1 \\[1mm]
q_2 & 0 \rightarrow q_3 \\[1mm]
q_2 & 1 \rightarrow q_3 \\[1mm]
q_3 & 1 \rightarrow q_2
\end{array}
\]

---

#### 1. Zustände von \(M_1'\)

\[
Q' = \{\,q_i^k \mid i\in\{1,2,3\},\; k\in\{0,1,2\}\,\}
\]

z. B. \(q_1^0, q_1^1, q_1^2, q_2^0,\dots , q_3^2\).

#### 2. Start- und Endzustände

\[
q_0' = q_1^0,\qquad
F' = \{\, q_3^2 \,\}
\]

#### 3. Übergangs­funktion \(\delta'\)

*Normale Übergänge (Zähler bleibt unverändert)*  

\[
\begin{aligned}
\delta'(q_1^k,0) &\ni q_2^k && (k=0,1,2)\\
\delta'(q_2^k,1) &\ni q_1^k && (k=0,1,2)\\
\delta'(q_2^k,0) &\ni q_3^k && (k=0,1,2)\\
\delta'(q_2^k,1) &\ni q_3^k && (k=0,1,2)\\
\delta'(q_3^k,1) &\ni q_2^k && (k=0,1,2)
\end{aligned}
\]

*„Überspring‑Übergänge“ (Verbrauch eines ‘0’ und Zähler‑Erhöhung)*  

\[
\begin{aligned}
\delta'(q_i^0,0) &\ni q_i^1 &&\text{für } i=1,2,3\\
\delta'(q_i^1,0) &\ni q_i^2 &&\text{für } i=1,2,3
\end{aligned}
\]

(Es gibt **keine** Überspring‑Übergänge mehr, wenn bereits zwei Nullen gelöscht wurden, d. h. für \(k=2\) gibt es keinen solchen Zusatz‑Übergang.)

---

#### 4. Ergebnis‑Diagramm (textuelle Darstellung)

```
          0                0                0
   q1^0 ──► q2^0 ◀─► q2^0 ──► q3^0
    │      ▲  │     ▲   │
    │      │ 0 1|   1│   (normal)
    │      │  │     │
    │      │  ▼     ▼
    │  (skip 0)  (skip 0)
    │      │     │
    ▼      ▼     ▼
   q1^1 → q2^1 → q3^1   (analog für k=2)
```

In Worten:  
Aus jedem Zustand \(q_i^k\) gibt es einen **normale** Übergang wie im originalen NFA, der den Zähler nicht ändert, und zusätzlich einen **„skip“-Übergang** bei Eingabe ‘0’, der den Zähler von 0→1 bzw. 1→2 erhöht und den Zustand unverändert lässt. Sobald der Zähler den Wert 2 erreicht hat, dürfen nur noch die normalen Übergänge verwendet werden, und nur wenn der aktuelle Zustand zu den ursprünglichen Endzuständen gehört (hier \(q_3\)), wird das Wort akzeptiert.  

Damit ist ein $\epsilon$‑NFA \(M'\) konstruiert, das genau die Sprache \(L(M)^{\downarrow 0}\) akzeptiert, und das Ergebnis für den konkreten NFA \(M_1\) wurde vollständig angegeben.






Subproblem c (3.0/3.0P) 






Es gilt weiterhin Σ={0,1}\Sigma=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet L↑0L^{\uparrow 0} die Sprache, die man erhält, wenn man den Wörtern aus LL jeweils zwei Nullen hinzufügt. Formal gilt
L↑0:={u0v0w∣uvw∈L∧u,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 L↑0≠LL^{\uparrow 0}\neq L.
Falls Sie die Aussage mit einem Gegenbeispiel widerlegen möchten, zeigen Sie auch die Korrektheit des Gegenbeispiels.




☒Wahr☐Falsch



Beweis, dass für jede nichtleere Sprache L⊆{0,1}∗L\subseteq\{0,1\}^* stets L↑0≠LL^{\uparrow0}\neq L gilt

Sei L≠∅L\neq\varnothing.  
Betrachte die Menge der Längen aller Wörter von LL:
ℓ(L)={ ∣w∣∣w∈L }⊆N.
\ell(L)=\{\,|w|\mid w\in L\,\}\subseteq\mathbb N .

Da N\mathbb N wohlgeordnet ist, besitzt ℓ(L)\ell(L) ein Minimum.
Sei also w∈Lw\in L ein Wort mit minimaler Länge n=∣w∣n=|w|.

Für jedes Wort x∈L↑0x\in L^{\uparrow0} gibt es laut Definition Wörter
u,v∈Σ∗u,v\in\Sigma^* und ein Wort y∈Ly\in L mit
x=u0v0wundy=uvw.
x = u0v0w\quad\text{und}\quad y = uvw .

Damit ist ∣x∣=∣y∣+2|x| = |y|+2. Da y∈Ly\in L, gilt ∣y∣≥n|y|\ge n (wegen der Minimalität von ww).
Folglich ∣x∣≥n+2|x| \ge n+2.

Insbesondere hat jedes Wort aus L↑0L^{\uparrow0} eine Länge von mindestens
n+2n+2. Das Wort ww hat jedoch Länge nn und kann deshalb nicht in
L↑0L^{\uparrow0} liegen. Also ist w∈L∖L↑0w\in L\setminus L^{\uparrow0} und damit
L≠L↑0L\neq L^{\uparrow0}.

Damit ist die Aussage wahr: Für jede nichtleere Sprache L⊆Σ∗L\subseteq\Sigma^*
gilt L↑0≠LL^{\uparrow0}\neq L.■ \blacksquare 








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:
1. **Zustände**: i, 1, 2, 3, f  
   **Kanten**:  
   - i → 1 : ε  
   - 1 → 2 : a   1 → 3 : b  
   - 2 → 1 : a  
   - 3 → 3 : a   3 → 2 : b  
   - 3 → f : ε  

   **Entferne Zustand 1** (keine Schleife auf 1).  
   Neue Kanten nach Regel \(p\!\to\!q = \alpha\beta^{*}\gamma\):  

   - i → 2 : ε·a = **a**  
   - i → 3 : ε·b = **b**  
   - 2 → 2 : a·a = **aa**  
   - 2 → 3 : a·b = **ab**  

   Ergebnis‑Automat (Zustände i, 2, 3, f):  

   - i → 2 : a  
   - i → 3 : b  
   - 2 → 2 : aa  
   - 2 → 3 : ab  
   - 3 → 3 : a   3 → 2 : b  
   - 3 → f : ε  

2. **Entferne Zustand 2** (Schleife β = aa).  

   Für jeden Eingang \(p\!\to\!2 = \alpha\) und Ausgang \(2\!\to\!q = \gamma\) wird  
   \(p\!\to\!q = \alpha\,\beta^{*}\,\gamma\) hinzugefügt.

   - i → 3 : a · (aa)^{*} · ab  → **a (aa)^{*} ab**  
   - 3 → 3 : b · (aa)^{*} · ab  → **b (aa)^{*} ab**  

   Diese werden zu den bereits vorhandenen Kanten vereinigt (Union “+”):

   - i → 3 : **b + a (aa)^{*} ab**  
   - 3 → 3 : **a + b (aa)^{*} ab**  

   Ergebnis‑Automat (Zustände i, 3, f):  

   - i → 3 : b + a (aa)^{*} ab  
   - 3 → 3 : a + b (aa)^{*} ab  
   - 3 → f : ε  

3. **Entferne Zustand 3** (Schleife β = a + b (aa)^{*} ab).  

   - i → f : (b + a (aa)^{*} ab) · ( a + b (aa)^{*} ab )^{*} · ε  
     → **(b + a (aa)^{*} ab)(a + b (aa)^{*} ab)^{*}**

   Nach Entfernung aller Zwischenzustände bleibt nur die Kante i → f.

Regulärer Ausdruck: $r = (b + a (aa)^{*} ab)(a + b (aa)^{*} ab)^{*}$






Subproblem b (0.0/3.0P) 






Geben Sie eine rechtslineare Grammatik für L(N)L(N) mit höchstens 3 Nichtterminalen an.

Hinweis: In rechtslinearen Grammatiken sind keine ε\varepsilon-Produktionen außer S→εS \to \varepsilon erlaubt.





<empty>


no answer given










Exercise 5: Kontextfreie Sprachen


Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=j∨j=k)∧i,j,k≥0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:w∈Σ∗∧∣w∣≥n∧n>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+k∧i,j,k≥0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}





Subproblem a (0.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}  
SS ist der Startsymbol.  

S→M∣NM→a M b∣TT→a T∣εN→a N∣VV→b V a∣ε
\begin{aligned}
S &\to M \mid N\\
M &\to a\,M\,b \mid T\\
T &\to a\,T \mid \varepsilon\\
N &\to a\,N \mid V\\
V &\to b\,V\,a \mid \varepsilon
\end{aligned}


MM erzeugt aibiaka^{i}b^{i}a^{k} (Fall i=ji=j), NN erzeugt aibjaja^{i}b^{j}a^{j} (Fall j=kj=k).  

---

Grammatik für L2L_{2}  
SS ist der Startsymbol.

S→a S X∣a X YX→a∣bY→a Y∣b Y∣ε
\begin{aligned}
S &\to a\,S\,X \mid a\,X\,Y\\
X &\to a \mid b\\
Y &\to a\,Y \mid b\,Y \mid \varepsilon
\end{aligned}


Jede Ableitung liefert ana^{n} gefolgt von exakt nn Symbolen aus {a,b}\{a,b\} (durch die XX’s) und danach beliebig viele weitere Symbole (durch YY). Damit gilt ∣w∣≥n|w|\ge n und n>0n>0.

---

Grammatik für L3L_{3}  
SS ist der Startsymbol.

S→A BA→a A b∣εB→b B a∣b B∣b
\begin{aligned}
S &\to A\,B\\
A &\to a\,A\,b \mid \varepsilon\\
B &\to b\,B\,a \mid b\,B \mid b
\end{aligned}


AA erzeugt aibia^{i}b^{i}.  
BB erzeugt ein Wort der Form bmakb^{m}a^{k} mit m≥k+1m\ge k+1.  
Damit hat jedes Wort die Form aibi+maka^{i}b^{i+m}a^{k} und erfüllt
j=i+m>i+kj=i+m > i+k. Alle Bedingungen von L3L_{3} sind erfüllt.


answer does not follow the template








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_1☒L2L_2☐L3L_3





Regulärer Ausdruck: a(a|b)+


0: mismatch
0: could not parse value a(a|b)+ for type re








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,X→p,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)☒L1≠Lϵ(M)L_1\neq L_\epsilon(M)☐L2=Lϵ(M)L_2=L_\epsilon(M)☒L2≠Lϵ(M)L_2\neq L_\epsilon(M)☒L3=Lϵ(M)L_3=L_\epsilon(M)☐L3≠Lϵ(M)L_3\neq L_\epsilon(M)



L1L_1: a  
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 unentscheidbar☐LaL^a ist unentscheidbar☐Es 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?




☒w∉L(M)w \notin L(M)☐L(M)L(M) ist unentscheidbar☒L(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 L∈PL \in \text{P}. Dann gilt L‾∈NP\overline L \in \text{NP}.







Subproblem e (2.0/2.0P) 






Angenommen, P≠NP\text{P} \neq \text{NP}. Seien A,B⊆Σ∗A,B\subseteq\Sigma^* beliebige Sprachen, sodass A∈NPA \in \text{NP} und BB NP\text{NP}-vollständig ist. Welche Aussagen sind wahr?




☐A⊆BA \subseteq B☐B⊆AB \subseteq A☒A≤pBA \leq_p B☐B≤pAB \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 A∪BA \cup B und A∪B‾A \cup \overline B ist unentscheidbar.




☒Wahr☐Falsch



Beweis (Wahrheit der Aussage).

Seien A,B⊆Σ∗A,B\subseteq\Sigma^{*} beliebig und sei AA unentscheidbar.  
Wir zeigen, dass es unmöglich ist, dass beide Sprachen  

A∪BundA∪B‾
A\cup B \qquad\text{und}\qquad A\cup\overline{B}


entscheidbar sind.

Angenommen, sowohl A∪BA\cup B als auch A∪B‾A\cup\overline{B} seien entscheidbar.  
Die Klasse der entscheidbaren Sprachen ist unter Schnitt (Intersection) abgeschlossen.  
Betrachte daher den Schnitt beider Mengen:

(A∪B)  ∩  (A∪B‾)=A  ∪  (B∩B‾)=A  ∪  ∅=A.
\begin{aligned}
(A\cup B)\;\cap\;(A\cup\overline{B})
   &= A\;\cup\;(B\cap\overline{B}) \\
   &= A\;\cup\;\varnothing \\
   &= A .
\end{aligned}


Da beide Ausgangssprachen nach Annahme entscheidbar sind, wäre ihr Schnitt ebenfalls entscheidbar.  
Damit wäre AA entscheidbar – ein Widerspruch zur Voraussetzung, dass AA unentscheidbar ist.

Folglich kann nicht gleichzeitig gelten, dass A∪BA\cup B und A∪B‾A\cup\overline{B} entscheidbar sind.  
Damit ist garantiert, dass mindestens eine der beiden Sprachen unentscheidbar ist.

Die Aussage ist wahr.
\boxed{\text{Die Aussage ist wahr.}}









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 A≤pBA\le_p B für ein B∈PB\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 B≤pAB\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?




☐A∈PA\in\mathsf{P}☒AA ist NP\mathsf{NP}-hart



Reduktion: SAT≤pA\text{SAT}\le_p A

Begründung:
Gegeben sei eine CNF‑Formel FF (Instanz von SAT) über Variablenmenge VV.
Wir konstruieren drei Formeln F1,F2,F3F_1,F_2,F_3 über derselben Variablenmenge:

* F1:=FF_1 := F.
* F2:=(x∨¬x)F_2 := (x \lor \lnot x) für ein beliebiges x∈Vx\in V (eine Tautologie, also unter jeder Belegung erfüllt).
* F3:=(x)∧(¬x)F_3 := (x) \land (\lnot x) (ein Widerspruch; niemals erfüllt).

Die Konstruktion ist eindeutig in polynomialer Zeit möglich.

Nun gilt:

∃  σ:V→{0,1} mit genau zwei erfu¨llten Formeln among F1,F2,F3  Longleftrightarrow  σ erfu¨llt F1
\exists\;\sigma:V\to\{0,1\}\text{ mit genau zwei erfüllten Formeln among }F_1,F_2,F_3
\iff
\sigma \text{ erfüllt }F_1


denn F2F_2 ist immer erfüllt und F3F_3 ist nie erfüllt.  
Somit gibt es eine solche Belegung genau dann, wenn FF erfüllbar ist, d.h. genau dann, wenn die SAT‑Instanz mit „Ja“ beantwortet wird.

Damit ist die Abbildung F↦(F1,F2,F3)F \mapsto (F_1,F_2,F_3) eine polynomialzeit‑Reduktion von SAT auf das gegebene Problem AA. Da SAT NP‑hart ist, ist AA ebenfalls NP‑hart (und liegt offensichtlich in NP, also ist AA NP‑vollständig).






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<j≤ni<j \leq n mit σ(xi)=1=σ(xj)\sigma(x_i)=1= \sigma(x_j)?




☒A∈PA\in\mathsf{P}☐AA ist NP\mathsf{NP}-hart



Reduktion: A≤p2SATA\le_p \mathsf{2SAT}  

Begründung:  
Gegeben sei eine Instanz des Problems AA, also  
* eine 2‑KNF‑Formel FF über den Variablen V={x1,…,xn}V=\{x_1,\dots ,x_n\},  
* eine Farbfunktion g:V→{1,…,l}g:V\to\{1,\dots ,l\}.

Wir konstruieren in polynomialer Zeit eine neue 2‑KNF‑Formel F′F' wie folgt  

F′  :=  F  ∧  ⋀i<jg(xi)=g(xj)(¬xi ∨ ¬xj).
F' \;:=\; F\;\land\;\bigwedge_{\substack{i<j\\ g(x_i)=g(x_j)}}(\lnot x_i \,\lor\, \lnot x_j).


Der zweite Teil besteht aus allen Paar‑Klauseln, die für jedes Farb‑Kollektiv cc genau die Aussage „es können nicht beide Variablen derselben Farbe wahr sein“ ausdrücken.  
Da jede dieser Klauseln nur zwei Literale besitzt, ist F′F' wieder eine 2‑KNF‑Formel.  
Die Anzahl der hinzugefügten Klauseln ist höchstens (n2)\binom{n}{2}, also polynomial in nn; die Konstruktion ist daher polynomialzeit­machbar.

Nun gilt:

Wenn es eine Belegung σ\sigma gibt, die FF erfüllt und bei der alle wahr gesetzten Variablen unterschiedliche Farben besitzen, dann erfüllt σ\sigma per Definition jede der Klauseln (¬xi∨¬xj)(\lnot x_i\lor\lnot x_j) für Variablen mit gleicher Farbe – weil höchstens eine von ihnen wahr ist. Also erfüllt σ\sigma auch F′F'.  

Umgekehrt: Erfüllt eine Belegung σ\sigma die Formel F′F', dann erfüllt sie zunächst FF (da FF ein Teil von F′F' ist) und sie verletzt keine der Klauseln (¬xi∨¬xj)(\lnot x_i\lor\lnot x_j). Letztere Klauseln verhindern genau, dass zwei Variablen derselben Farbe gleichzeitig wahr sind. Deshalb besitzt σ\sigma die geforderte Eigenschaft, dass alle wahren Variablen unterschiedliche Farben haben.

Damit ist

∃  σ mit den Bedingungen von ALongleftrightarrowF′ ist erfu¨llbar.
\exists\;\sigma\text{ mit den Bedingungen von }A\quad\Longleftrightarrow\quad F' \text{ ist erfüllbar}.


Die Abbildung (F,g)↦F′(F,g)\mapsto F' ist eine polynomialzeit‑Reduktion von AA auf das klassische 2SAT\mathsf{2SAT}-Entscheidungsproblem. Da 2SAT∈P\mathsf{2SAT}\in\mathsf{P} ist, folgt, dass A∈PA\in\mathsf{P} (und naturgemäß liegt AA in NP).

A∈P
\boxed{A\in\mathsf{P}}









Exercise 8: Bonus


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

Mindestens eine Antwortmöglichkeit ist immer richtig.





Subproblem a (0.0/2.0P) 






Sei Σ:={a,b}\Sigma := \{a,b\}. Für welche der folgenden Sprachen LiL_i, wobei i∈{1,2,3}i\in\{1,2,3\}, gilt, dass (Li)∗(L_i)^* nicht regulär ist? (Es können mehrere sein.) Wählen Sie ein solches ii und begründen Sie kurz, dass (Li)∗(L_i)^* nicht regulär ist.






☐L1:={(ab)n: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.