anthropic/claude-opus-4.1

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

δ′\delta':
For all q∈Qq \in Q, i∈{0,1,2}i \in \{0, 1, 2\}:
- δ′((q,i),1):={(p,i)∣p∈δ(q,1)}\delta'((q, i), 1) := \{(p, i) \mid p \in \delta(q, 1)\}
- δ′((q,i),0):={(p,i)∣p∈δ(q,0)}\delta'((q, i), 0) := \{(p, i) \mid p \in \delta(q, 0)\}
- δ′((q,i),ϵ):={{(p,i+1)∣p∈δ(q,0)}if i∈{0,1}∅if i=2\delta'((q, i), \epsilon) := \begin{cases}
  \{(p, i+1) \mid p \in \delta(q, 0)\} & \text{if } i \in \{0, 1\} \\
  \emptyset & \text{if } i = 2
  \end{cases}

Konstruktionsidee (optional):
The construction creates three "layers" of the original NFA, where each layer tracks how many zeros have been removed so far. The second component i∈{0,1,2}i \in \{0, 1, 2\} counts the number of zeros removed. On reading a 0, we can either follow the original transition (keeping the count) or skip it via an ε-transition (incrementing the count). On reading a 1, we simply follow the original transition. We accept only when we reach a final state of M after removing exactly 2 zeros.

Ihr Konstruktionsergebnis für M1M_1:
States: (q1,0),(q1,1),(q1,2),(q2,0),(q2,1),(q2,2),(q3,0),(q3,1),(q3,2)(q_1,0), (q_1,1), (q_1,2), (q_2,0), (q_2,1), (q_2,2), (q_3,0), (q_3,1), (q_3,2)
Start state: (q1,0)(q_1,0)
Final state: (q3,2)(q_3,2)

Transitions:
From (q1,0)(q_1,0): 0→(q2,0)0 \to (q_2,0), ϵ→(q2,1)\epsilon \to (q_2,1)
From (q1,1)(q_1,1): 0→(q2,1)0 \to (q_2,1), ϵ→(q2,2)\epsilon \to (q_2,2)
From (q1,2)(q_1,2): 0→(q2,2)0 \to (q_2,2)

From (q2,0)(q_2,0): 1→{(q1,0),(q3,0)}1 \to \{(q_1,0), (q_3,0)\}, 0→(q3,0)0 \to (q_3,0), ϵ→(q3,1)\epsilon \to (q_3,1)
From (q2,1)(q_2,1): 1→{(q1,1),(q3,1)}1 \to \{(q_1,1), (q_3,1)\}, 0→(q3,1)0 \to (q_3,1), ϵ→(q3,2)\epsilon \to (q_3,2)
From (q2,2)(q_2,2): 1→{(q1,2),(q3,2)}1 \to \{(q_1,2), (q_3,2)\}, 0→(q3,2)0 \to (q_3,2)

From (q3,0)(q_3,0): 1→(q2,0)1 \to (q_2,0)
From (q3,1)(q_3,1): 1→(q2,1)1 \to (q_2,1)
From (q3,2)(q_3,2): 1→(q2,2)1 \to (q_2,2)

Subproblem c (3.0/3.0P)

Es gilt weiterhin Σ={0,1}\Sigma=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet 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
Proof that the statement is true:

For any non-empty language L⊆Σ∗L \subseteq \Sigma^*, I will show that L↑0≠LL^{\uparrow 0} \neq L.

Since LL is non-empty, there exists at least one word in LL. Let w∈Lw \in L be a word with the minimum number of zeros among all words in LL. Let's say ww contains exactly kk zeros.

Key observation: Every word in L↑0L^{\uparrow 0} is formed by adding exactly 2 zeros to some word from LL. Since every word in LL has at least kk zeros, every word in L↑0L^{\uparrow 0} has at least k+2k + 2 zeros.

Now I consider two cases:

Case 1: k<2k < 2 (i.e., ww has 0 or 1 zeros)
- Then w∈Lw \in L has fewer than 2 zeros
- But every word in L↑0L^{\uparrow 0} has at least k+2≥2k + 2 \geq 2 zeros
- Therefore w∈Lw \in L but w∉L↑0w \notin L^{\uparrow 0}
- Hence L⊈L↑0L \not\subseteq L^{\uparrow 0}, so L≠L↑0L \neq L^{\uparrow 0}

Case 2: k≥2k \geq 2 (i.e., all words in LL have at least 2 zeros)
- For ww to be in L↑0L^{\uparrow 0}, we would need w=u0v0zw = u0v0z for some uvz∈Luvz \in L
- But then uvzuvz would have exactly k−2k - 2 zeros
- This contradicts our assumption that kk is the minimum number of zeros in any word in LL
- Therefore w∈Lw \in L but w∉L↑0w \notin L^{\uparrow 0}
- Hence L⊈L↑0L \not\subseteq L^{\uparrow 0}, so L≠L↑0L \neq L^{\uparrow 0}

In both cases, we have L≠L↑0L \neq L^{\uparrow 0}. Therefore, the statement is true.

anthropic/claude-sonnet-4

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 (2.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=(0∣1)∗1s_3=(0\mid 1)^*1
2: wrong language: contains 1

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

δ′\delta':
For all q∈Qq \in Q and a∈{0,1}a \in \{0, 1\}:
- δ′((q,0),a):={(p,0):p∈δ(q,a)}\delta'((q, 0), a) := \{(p, 0) : p \in \delta(q, a)\}
- δ′((q,0),ϵ):={(p,1):p∈δ(q,0)}\delta'((q, 0), \epsilon) := \{(p, 1) : p \in \delta(q, 0)\}
- δ′((q,1),a):={(p,1):p∈δ(q,a)}\delta'((q, 1), a) := \{(p, 1) : p \in \delta(q, a)\}
- δ′((q,1),ϵ):={(p,2):p∈δ(q,0)}\delta'((q, 1), \epsilon) := \{(p, 2) : p \in \delta(q, 0)\}
- δ′((q,2),a):={(p,2):p∈δ(q,a)}\delta'((q, 2), a) := \{(p, 2) : p \in \delta(q, a)\}

Konstruktionsidee (optional):
The states (q,i)(q, i) track the current state qq of the original automaton and how many 0's we have "virtually consumed" (i=0,1,2i = 0, 1, 2). We start in phase 0, use ε-transitions to simulate the first 0 (moving to phase 1), then the second 0 (moving to phase 2), and only accept in phase 2 when in a final state of the original automaton.

Ihr Konstruktionsergebnis für M1M_1:

States: (q1,0),(q1,1),(q1,2),(q2,0),(q2,1),(q2,2),(q3,0),(q3,1),(q3,2)(q_1, 0), (q_1, 1), (q_1, 2), (q_2, 0), (q_2, 1), (q_2, 2), (q_3, 0), (q_3, 1), (q_3, 2)
Start state: (q1,0)(q_1, 0)
Final state: (q3,2)(q_3, 2)

Transitions:
- (q1,0)→0(q2,0)(q_1, 0) \xrightarrow{0} (q_2, 0)
- (q1,0)→ϵ(q2,1)(q_1, 0) \xrightarrow{\epsilon} (q_2, 1)
- (q1,1)→0(q2,1)(q_1, 1) \xrightarrow{0} (q_2, 1)
- (q1,1)→ϵ(q2,2)(q_1, 1) \xrightarrow{\epsilon} (q_2, 2)
- (q1,2)→0(q2,2)(q_1, 2) \xrightarrow{0} (q_2, 2)
- (q2,0)→0(q3,0)(q_2, 0) \xrightarrow{0} (q_3, 0)
- (q2,0)→1(q1,0),(q3,0)(q_2, 0) \xrightarrow{1} (q_1, 0), (q_3, 0)
- (q2,0)→ϵ(q3,1)(q_2, 0) \xrightarrow{\epsilon} (q_3, 1)
- (q2,1)→0(q3,1)(q_2, 1) \xrightarrow{0} (q_3, 1)
- (q2,1)→1(q1,1),(q3,1)(q_2, 1) \xrightarrow{1} (q_1, 1), (q_3, 1)
- (q2,1)→ϵ(q3,2)(q_2, 1) \xrightarrow{\epsilon} (q_3, 2)
- (q2,2)→0(q3,2)(q_2, 2) \xrightarrow{0} (q_3, 2)
- (q2,2)→1(q1,2),(q3,2)(q_2, 2) \xrightarrow{1} (q_1, 2), (q_3, 2)
- (q3,0)→1(q2,0)(q_3, 0) \xrightarrow{1} (q_2, 0)
- (q3,1)→1(q2,1)(q_3, 1) \xrightarrow{1} (q_2, 1)
- (q3,2)→1(q2,2)(q_3, 2) \xrightarrow{1} (q_2, 2)

Subproblem c (3.0/3.0P)

Es gilt weiterhin Σ={0,1}\Sigma=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet 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
The statement is true.

Proof by contradiction:

Suppose there exists a nonempty language LL such that L=L↑0L = L^{\uparrow 0}.

Case 1: If ε∈L\varepsilon \in L, then since L=L↑0L = L^{\uparrow 0}, we have ε∈L↑0\varepsilon \in L^{\uparrow 0}. This means ε=u0v0w\varepsilon = u0v0w for some u,v,w∈Σ∗u,v,w \in \Sigma^* with uvw∈Luvw \in L. But this is impossible since u0v0wu0v0w has length at least 2 while ε\varepsilon has length 0.

Case 2: If ε∉L\varepsilon \notin L, let w∈Lw \in L be a string of minimum positive length. Since w∈L↑0w \in L^{\uparrow 0}, we have w=u0v0zw = u0v0z where uvz∈Luvz \in L. But then ∣uvz∣=∣w∣−2<∣w∣|uvz| = |w| - 2 < |w|, contradicting the minimality of ∣w∣|w|.

Therefore, no such language LL exists, proving L↑0≠LL^{\uparrow 0} \neq L for all nonempty languages LL.

deepseek/deepseek-chat-v3.1

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

δ′\delta':
For all q∈Qq \in Q, k∈{0,1,2}k \in \{0,1,2\}, and a∈Σa \in \Sigma:
- δ′((q,k),a)={(p,k)∣p∈δ(q,a)}\delta'((q, k), a) = \{ (p, k) \mid p \in \delta(q, a) \}

For all q∈Qq \in Q and k∈{0,1}k \in \{0,1\}:
- δ′((q,k),ϵ)={(p,k+1)∣p∈δ(q,0)}\delta'((q, k), \epsilon) = \{ (p, k+1) \mid p \in \delta(q, 0) \}

Konstruktionsidee (optional):
Die Konstruktion simuliert den ursprünglichen NFA MM und erlaubt nicht-deterministisch das Überspringen von genau zwei Nullen. Jeder Zustand in M′M' ist ein Paar (q,k)(q, k), wobei qq den Zustand in MM und kk die Anzahl der bisher übersprungenen Nullen (0, 1 oder 2) repräsentiert. Über Σ\Sigma-Transitionen wird MM normal simuliert ohne kk zu ändern. ϵ\epsilon-Transitionen erlauben das Überspringen einer Null (falls k<2k < 2), was kk erhöht und zu den Zuständen führt, die in MM beim Lesen einer Null von qq erreichbar sind. Endzustände sind solche, in denen MM in einem Finalzustand ist und genau zwei Nullen übersprungen wurden.

Ihr Konstruktionsergebnis für M1M_1:
Zustände: (q1,0), (q1,1), (q1,2), (q2,0), (q2,1), (q2,2), (q3,0), (q3,1), (q3,2)  
Startzustand: (q1,0)  
Finalzustände: (q3,2)  

Transitionen:
- (q1,0), 0 → (q2,0)
- (q1,0), ε → (q2,1)
- (q1,1), 0 → (q2,1)
- (q1,1), ε → (q2,2)
- (q1,2), 0 → (q2,2)
- (q2,0), 0 → (q3,0)
- (q2,0), 1 → (q1,0), (q3,0)
- (q2,0), ε → (q3,1)
- (q2,1), 0 → (q3,1)
- (q2,1), 1 → (q1,1), (q3,1)
- (q2,1), ε → (q3,2)
- (q2,2), 0 → (q3,2)
- (q2,2), 1 → (q1,2), (q3,2)
- (q3,0), 1 → (q2,0)
- (q3,1), 1 → (q2,1)
- (q3,2), 1 → (q2,2)

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
Die Aussage ist wahr. Für jede nichtleere Sprache L⊆Σ∗L \subseteq \Sigma^* gilt L↑0≠LL^{\uparrow 0} \neq L.

Beweis:  
Angenommen, für eine nichtleere Sprache LL gilt L↑0=LL^{\uparrow 0} = L. Dann muss insbesondere L⊆L↑0L \subseteq L^{\uparrow 0} gelten. Das bedeutet, dass jedes Wort w∈Lw \in L in der Form w=u0v0w′w = u0v0w' für einige u,v,w′∈Σ∗u, v, w' \in \Sigma^* geschrieben werden kann, sodass uvw′∈Lu v w' \in L. Daher muss jedes Wort in LL mindestens zwei Nullen enthalten.

Sei m=min⁡{Anzahl der Nullen in w∣w∈L}m = \min\{ \text{Anzahl der Nullen in } w \mid w \in L \}. Da LL nichtleer ist, ist mm wohldefiniert und m≥2m \geq 2. Wähle ein Wort w∈Lw \in L mit genau mm Nullen. Da w∈L↑0w \in L^{\uparrow 0}, existieren u,v,w′∈Σ∗u, v, w' \in \Sigma^* mit w=u0v0w′w = u0v0w' und uvw′∈Lu v w' \in L. Das Wort uvw′u v w' hat jedoch m−2m - 2 Nullen, da zwei Nullen entfernt wurden. Da mm die minimale Anzahl von Nullen in LL ist, muss uvw′u v w' mindestens mm Nullen haben, aber m−2<mm - 2 < m für m≥2m \geq 2, was ein Widerspruch ist. Daher kann L⊆L↑0L \subseteq L^{\uparrow 0} nicht gelten, und somit ist L↑0≠LL^{\uparrow 0} \neq L für jede nichtleere Sprache LL.

deepseek/deepseek-r1-0528

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

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

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

Ihr Konstruktionsergebnis für M1M_1:
- Zustände: (q1,0)(q_1,0), (q1,1)(q_1,1), (q1,2)(q_1,2), (q2,0)(q_2,0), (q2,1)(q_2,1), (q2,2)(q_2,2), (q3,0)(q_3,0), (q3,1)(q_3,1), (q3,2)(q_3,2)
- Start: (q1,0)(q_1,0)
- Ende: (q3,2)(q_3,2)
- Transitionen (in Tripelform):
  (q1,0,0)→(q2,0)(q_1,0,0) \to (q_2,0), (q1,0,0)→(q1,1)(q_1,0,0) \to (q_1,1)
  (q1,1,0)→(q2,1)(q_1,1,0) \to (q_2,1), (q1,1,0)→(q1,2)(q_1,1,0) \to (q_1,2)
  (q1,2,0)→(q2,2)(q_1,2,0) \to (q_2,2)
  (q2,0,0)→(q3,0)(q_2,0,0) \to (q_3,0), (q2,0,0)→(q2,1)(q_2,0,0) \to (q_2,1)
  (q2,0,1)→(q1,0)(q_2,0,1) \to (q_1,0), (q2,0,1)→(q3,0)(q_2,0,1) \to (q_3,0)
  (q2,1,0)→(q3,1)(q_2,1,0) \to (q_3,1), (q2,1,0)→(q2,2)(q_2,1,0) \to (q_2,2)
  (q2,1,1)→(q1,1)(q_2,1,1) \to (q_1,1), (q2,1,1)→(q3,1)(q_2,1,1) \to (q_3,1)
  (q2,2,0)→(q3,2)(q_2,2,0) \to (q_3,2)
  (q2,2,1)→(q1,2)(q_2,2,1) \to (q_1,2), (q2,2,1)→(q3,2)(q_2,2,1) \to (q_3,2)
  (q3,0,0)→(q3,1)(q_3,0,0) \to (q_3,1)
  (q3,0,1)→(q2,0)(q_3,0,1) \to (q_2,0)
  (q3,1,0)→(q3,2)(q_3,1,0) \to (q_3,2)
  (q3,1,1)→(q2,1)(q_3,1,1) \to (q_2,1)
  (q3,2,1)→(q2,2)(q_3,2,1) \to (q_2,2)

Subproblem c (3.0/3.0P)

Es gilt weiterhin Σ={0,1}\Sigma=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet 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
Die Aussage ist wahr: Für jede nichtleere Sprache L⊆Σ∗ L \subseteq \Sigma^*  gilt L↑0≠L L^{\uparrow 0} \neq L .

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

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

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

In beiden Fällen folgt die Behauptung.

google/gemini-2.5-pro

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

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

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

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

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

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

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

Subproblem c (3.0/3.0P)

Es gilt weiterhin Σ={0,1}\Sigma=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet 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
Die Aussage ist wahr.

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

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

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

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

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

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

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

openai/gpt-5

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

δ′\delta':
Für alle q∈Qq\in Q, i∈{0,1,2}i\in\{0,1,2\}, a∈{0,1}a\in\{0,1\}:
- δ′((q,i),a):={(p,i)∣p∈δ(q,a)}\delta'((q,i),a):=\{(p,i)\mid p\in\delta(q,a)\}
- δ′((q,0),ϵ):={(p,1)∣p∈δ(q,0)}\delta'((q,0),\epsilon):=\{(p,1)\mid p\in\delta(q,0)\}
- δ′((q,1),ϵ):={(p,2)∣p∈δ(q,0)}\delta'((q,1),\epsilon):=\{(p,2)\mid p\in\delta(q,0)\}
- δ′((q,2),ϵ):=∅\delta'((q,2),\epsilon):=\emptyset

Konstruktionsidee (optional):
Wir simulieren MM und dürfen genau zweimal eine zusätzliche 0 „einspeisen“, ohne ein Eingabesymbol zu verbrauchen. Ein Zähler i∈{0,1,2}i\in\{0,1,2\} in den Zuständen zählt, wie viele solcher Einspeisungen bereits erfolgt sind. Epsilon-Kanten entsprechen dem Lesen einer 0 in MM ohne Eingabeverbrauch und erhöhen den Zähler. Akzeptiert wird nur, wenn genau zwei Einspeisungen erfolgt sind.

Ihr Konstruktionsergebnis für M1M_1:
- Zustände: {(q1,i),(q2,i),(q3,i)∣i=0,1,2}\{(q1,i),(q2,i),(q3,i)\mid i=0,1,2\}
- Startzustand: (q1,0)(q1,0)
- Finalzustände: {(q3,2)}\{(q3,2)\}
- Konsumierende Kanten (für jedes i∈{0,1,2}i\in\{0,1,2\}):
  - (q1,i)→0(q2,i)(q1,i)\xrightarrow{0}(q2,i)
  - (q2,i)→0(q3,i)(q2,i)\xrightarrow{0}(q3,i)
  - (q2,i)→1(q1,i)(q2,i)\xrightarrow{1}(q1,i)
  - (q2,i)→1(q3,i)(q2,i)\xrightarrow{1}(q3,i)
  - (q3,i)→1(q2,i)(q3,i)\xrightarrow{1}(q2,i)
- Epsilon-Kanten (eingefügte 0, erhöhen den Zähler):
  - (q1,0)→ϵ(q2,1)(q1,0)\xrightarrow{\epsilon}(q2,1)
  - (q2,0)→ϵ(q3,1)(q2,0)\xrightarrow{\epsilon}(q3,1)
  - (q1,1)→ϵ(q2,2)(q1,1)\xrightarrow{\epsilon}(q2,2)
  - (q2,1)→ϵ(q3,2)(q2,1)\xrightarrow{\epsilon}(q3,2)

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
Angenommen, es gäbe eine nichtleere Sprache L mit L^{\uparrow 0}=L. Wähle w∈L mit minimaler Anzahl an Nullen, d.h. minimalem |w|_0. Aus w∈L^{\uparrow 0} folgt: Es gibt u,v,x∈Σ^* und w'∈L mit w=u0v0x und w'=uvx. Dann gilt |w'|_0=|w|_0−2, also w'∈L hat strikt weniger Nullen als w — Widerspruch zur Minimalität von |w|_0. Also kann für keine nichtleere L die Gleichheit L^{\uparrow 0}=L gelten. Damit ist die Aussage wahr.

openai/gpt-oss-120b

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 

qwen/qwen3-235b-a22b

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 (0.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\}.
s₁=ε  
s₂=(0|1)*  
s₃=(0 1 1* | 1)*
answer does not follow the template

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

δ′\delta':  
Für jede Transition q→apq \xrightarrow{a} p in MM:  
- Für alle c∈{0,1,2}c \in \{0,1,2\}:  
  - Falls a=1a = 1, füge ((q,c),1,(p,c))( (q,c), 1, (p,c) ) hinzu.  
  - Falls a=0a = 0, füge ((q,c),0,(p,c))( (q,c), 0, (p,c) ) hinzu.  
- Falls a=0a = 0 und c<2c < 2, füge ((q,c),ϵ,(p,c+1))( (q,c), \epsilon, (p,c+1) ) hinzu.  

Konstruktionsidee (optional):  
Der ε-NFA M′M' simuliert MM in drei Schichten, wobei jede Schicht die Anzahl der bisher entfernten Nullen (0, 1 oder 2) repräsentiert. Bei jeder Transition von MM auf Eingabe aa wird diese in der aktuellen Schicht verarbeitet. Zusätzlich kann bei a=0a=0 eine ε-Transition in die nächsthöhere Schicht eingefügt werden, um eine Null zu entfernen. Akzeptiert wird nur in der Schicht 2, da genau zwei Nullen entfernt werden müssen.  

Ihr Konstruktionsergebnis für M1M_1:  
Zustände: (q1,0),(q1,1),(q1,2),(q2,0),(q2,1),(q2,2),(q3,0),(q3,1),(q3,2)(q1,0), (q1,1), (q1,2), (q2,0), (q2,1), (q2,2), (q3,0), (q3,1), (q3,2)  
Startzustand: (q1,0)(q1,0)  
Finalzustände: (q3,2)(q3,2)  
Transitionen:  
- (q1,0)→0(q2,0)(q1,0) \xrightarrow{0} (q2,0)  
- (q1,1)→0(q2,1)(q1,1) \xrightarrow{0} (q2,1)  
- (q1,2)→0(q2,2)(q1,2) \xrightarrow{0} (q2,2)  
- (q1,0)→ϵ(q2,1)(q1,0) \xrightarrow{\epsilon} (q2,1)  
- (q1,1)→ϵ(q2,2)(q1,1) \xrightarrow{\epsilon} (q2,2)  
- (q2,0)→1(q1,0)(q2,0) \xrightarrow{1} (q1,0), (q2,1)→1(q1,1)(q2,1) \xrightarrow{1} (q1,1), (q2,2)→1(q1,2)(q2,2) \xrightarrow{1} (q1,2)  
- (q2,0)→0(q3,0)(q2,0) \xrightarrow{0} (q3,0), (q2,1)→0(q3,1)(q2,1) \xrightarrow{0} (q3,1), (q2,2)→0(q3,2)(q2,2) \xrightarrow{0} (q3,2)  
- (q2,0)→ϵ(q3,1)(q2,0) \xrightarrow{\epsilon} (q3,1), (q2,1)→ϵ(q3,2)(q2,1) \xrightarrow{\epsilon} (q3,2)  
- (q2,0)→1(q3,0)(q2,0) \xrightarrow{1} (q3,0), (q2,1)→1(q3,1)(q2,1) \xrightarrow{1} (q3,1), (q2,2)→1(q3,2)(q2,2) \xrightarrow{1} (q3,2)  
- (q3,0)→1(q2,0)(q3,0) \xrightarrow{1} (q2,0), (q3,1)→1(q2,1)(q3,1) \xrightarrow{1} (q2,1), (q3,2)→1(q2,2)(q3,2) \xrightarrow{1} (q2,2)

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
Die Aussage ist wahr. 

Beweis durch Widerspruch:  
Angenommen, es gäbe eine nichtleere Sprache L⊆Σ∗ L \subseteq \Sigma^*  mit L↑0=L L^{\uparrow 0} = L . Sei w∈L w \in L  ein Wort minimaler Länge m m . Da L↑0=L L^{\uparrow 0} = L , muss w∈L↑0 w \in L^{\uparrow 0}  gelten. Nach Definition von L↑0 L^{\uparrow 0}  existiert ein x∈L x \in L , sodass w w  durch Einfügen zweier Nullen in x x  entsteht. Dies impliziert ∣w∣=∣x∣+2 |w| = |x| + 2 . Da x∈L x \in L , gilt ∣x∣≥m |x| \geq m , also ∣w∣≥m+2 |w| \geq m + 2 . Dies widerspricht der Minimalität von m m , da w w  Länge m m  hat. Somit gibt es keine solche Sprache L L , und die Aussage ist bewiesen.

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

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

δ′\delta':  
- Für alle q∈Qq \in Q, k∈{0,1,2}k \in \{0,1,2\}, a∈Σa \in \Sigma:  
  δ′((q,k),a):={(p,k)∣p∈δ(q,a)}\delta'((q, k), a) := \{(p, k) \mid p \in \delta(q, a)\}  
- Für alle q∈Qq \in Q, k∈{0,1}k \in \{0,1\}:  
  δ′((q,k),ε):={(p,k+1)∣p∈δ(q,0)}\delta'((q, k), \varepsilon) := \{(p, k+1) \mid p \in \delta(q, 0)\}  

Konstruktionsidee (optional):  
Der ϵ\epsilon-NFA M′M' überwacht die Anzahl k∈{0,1,2}k \in \{0,1,2\} bereits simuliert "entfernter" Nullen durch Zustandserweiterung. Beim Lesen eines Symbols aa verbleibt M′M' im gleichen kk, sofern aa in der verkürzten Eingabe vorkommt (a∈{0,1}a \in \{0,1\}). Durch ϵ\epsilon-Übergänge simuliert M′M' das "Entfernen" einer Null aus der Originalsprache: bei Zustand (q,k)(q, k) mit k<2k < 2 folgt ein ϵ\epsilon-Übergang zu (p,k+1)(p, k+1), falls MM bei qq auf 00 zu pp gelangt. Nur bei k=2k=2 und einem akzeptierenden Zustand q∈Fq \in F wird die Eingabe akzeptiert.  

Ihr Konstruktionsergebnis für M1M_1:  
Q′={(q1,0),(q1,1),(q1,2),(q2,0),(q2,1),(q2,2),(q3,0),(q3,1),(q3,2)}Q' = \{(q_1,0), (q_1,1), (q_1,2), (q_2,0), (q_2,1), (q_2,2), (q_3,0), (q_3,1), (q_3,2)\}  
q0′=(q1,0)q_0' = (q_1, 0)  
F′={(q3,2)}F' = \{(q_3, 2)\}  
δ′\delta'-Übergänge:  
- Symbol-Transitionen:  
  - 00:  
    - (q1,k)→0(q2,k)(q_1, k) \xrightarrow{0} (q_2, k) für k=0,1,2k=0,1,2  
    - (q2,k)→0(q3,k)(q_2, k) \xrightarrow{0} (q_3, k) für k=0,1,2k=0,1,2  
  - 11:  
    - (q2,k)→1(q1,k),(q3,k)(q_2, k) \xrightarrow{1} (q_1, k), (q_3, k) für k=0,1,2k=0,1,2  
    - (q3,k)→1(q2,k)(q_3, k) \xrightarrow{1} (q_2, k) für k=0,1,2k=0,1,2  
- ϵ\epsilon-Transitionen:  
  - (q1,0)→ϵ(q2,1)(q_1, 0) \xrightarrow{\epsilon} (q_2, 1)  
  - (q1,1)→ϵ(q2,2)(q_1, 1) \xrightarrow{\epsilon} (q_2, 2)  
  - (q2,0)→ϵ(q3,1)(q_2, 0) \xrightarrow{\epsilon} (q_3, 1)  
  - (q2,1)→ϵ(q3,2)(q_2, 1) \xrightarrow{\epsilon} (q_3, 2)

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
Die Aussage ist wahr. Für jede nichtleere Sprache L⊆Σ∗L \subseteq \Sigma^* gilt L↑0≠LL^{\uparrow 0} \neq L. Sei n:=min⁡{∣w∣∣w∈L}n := \min \{ |w| \mid w \in L \}. Jedes Wort in L↑0L^{\uparrow 0} hat mindestens die Länge n+2n+2, da zwei Nullen zu einem Wort aus LL hinzugefügt werden. Da LL ein Wort der Länge nn enthält, während alle Wörter in L↑0L^{\uparrow 0} mindestens die Länge n+2n+2 haben, gilt L≠L↑0L \neq L^{\uparrow 0}.

x-ai/grok-4

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=\epsilon
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
Q′:=Q×{0,1,2}Q':=Q \times \{0,1,2\}
q0′:=(q0,0)q_0':=(q_0, 0)
F′:={(q,2)∣q∈F}F':=\{ (q,2) \mid q \in F \}

δ′\delta':
For all q∈Qq \in Q, k∈{0,1,2}k \in \{0,1,2\}, x∈Σx \in \Sigma:
δ′((q,k),x)={(p,k)∣p∈δ(q,x)}\delta'((q,k), x) = \{ (p, k) \mid p \in \delta(q, x) \}

For all q∈Qq \in Q, k∈{0,1}k \in \{0,1\}:
δ′((q,k),ϵ)={(p,k+1)∣p∈δ(q,0)}\delta'((q,k), \epsilon) = \{ (p, k+1) \mid p \in \delta(q, 0) \}

Konstruktionsidee (optional):
Die Konstruktion simuliert den NFA MM, wobei ϵ\epsilon-Transitionen verwendet werden, um genau zwei Nullen "einzufügen", ohne Eingabe zu konsumieren. Jede solche ϵ\epsilon-Transition simuliert eine Transition auf 0 im Original-NFA und erhöht den Zähler in der Zustandskomponente. Der Zähler stellt sicher, dass genau zwei Nullen eingefügt werden. Akzeptanz erfolgt nur in Zuständen (f,2)(f,2) mit f∈Ff \in F.

Ihr Konstruktionsergebnis für M1M_1:
Zustände: (q1,0)(q1,0), (q1,1)(q1,1), (q1,2)(q1,2), (q2,0)(q2,0), (q2,1)(q2,1), (q2,2)(q2,2), (q3,0)(q3,0), (q3,1)(q3,1), (q3,2)(q3,2)

Startzustand: (q1,0)(q1,0)

Finalzustände: (q3,2)(q3,2)

Transitionen auf 0:  
(q1,0)→(q2,0)(q1,0) \to (q2,0)  
(q1,1)→(q2,1)(q1,1) \to (q2,1)  
(q1,2)→(q2,2)(q1,2) \to (q2,2)  
(q2,0)→(q3,0)(q2,0) \to (q3,0)  
(q2,1)→(q3,1)(q2,1) \to (q3,1)  
(q2,2)→(q3,2)(q2,2) \to (q3,2)

Transitionen auf 1:  
(q2,0)→(q1,0)(q2,0) \to (q1,0), (q3,0)(q3,0)  
(q2,1)→(q1,1)(q2,1) \to (q1,1), (q3,1)(q3,1)  
(q2,2)→(q1,2)(q2,2) \to (q1,2), (q3,2)(q3,2)  
(q3,0)→(q2,0)(q3,0) \to (q2,0)  
(q3,1)→(q2,1)(q3,1) \to (q2,1)  
(q3,2)→(q2,2)(q3,2) \to (q2,2)

ϵ\epsilon-Transitionen:  
(q1,0)→(q2,1)(q1,0) \to (q2,1)  
(q1,1)→(q2,2)(q1,1) \to (q2,2)  
(q2,0)→(q3,1)(q2,0) \to (q3,1)  
(q2,1)→(q3,2)(q2,1) \to (q3,2)

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
Angenommen, es gibt eine nichtleere Sprache L⊆{0,1}∗L \subseteq \{0,1\}^* mit L=L↑0L = L^{\uparrow 0}.  
Da LL nichtleer ist, gibt es eine minimale Wortlänge m≥0m \geq 0, sodass LL ein Wort der Länge mm enthält, aber keines kürzeren.  
Jedes Wort in L↑0L^{\uparrow 0} entsteht durch das Einfügen von genau zwei Nullen in ein Wort aus LL und hat daher Länge mindestens m+2m+2.  
Folglich enthält L↑0L^{\uparrow 0} keine Wörter der Länge m<m+2m < m+2, im Widerspruch dazu, dass L=L↑0L = L^{\uparrow 0} Wörter der Länge mm enthält.  
Daher kann keine solche nichtleere Sprache LL existieren, und die Aussage ist wahr.

z-ai/glm-4.5

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 (2.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=(10)∗∣(10)∗1(01)∗∣(01)∗1s_3=(10)^*\mid(10)^*1(01)^*\mid(01)^*1
2: wrong language: contains 1

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
Q′={q(i):q∈Q,i∈{0,1,2}}Q'=\{q^{(i)} : q \in Q, i \in \{0, 1, 2\}\}
q0′=q0(0)q_0'=q_0^{(0)}
F′={q(2):q∈F}F'=\{q^{(2)} : q \in F\}

δ′\delta':
For each q∈Qq \in Q and i∈{0,1}i \in \{0, 1\}:
- For each x∈Σx \in \Sigma, δ′(q(i),x)={p(i):p∈δ(q,x)}\delta'(q^{(i)}, x) = \{p^{(i)} : p \in \delta(q, x)\}.
- δ′(q(i),ϵ)={p(i):p∈δ(q,ϵ)}∪{p(i+1):p∈δ(q,0)}\delta'(q^{(i)}, \epsilon) = \{p^{(i)} : p \in \delta(q, \epsilon)\} \cup \{p^{(i+1)} : p \in \delta(q, 0)\}.

For each q∈Qq \in Q:
- For each x∈Σ∪{ϵ}x \in \Sigma \cup \{\epsilon\}, δ′(q(2),x)={p(2):p∈δ(q,x)}\delta'(q^{(2)}, x) = \{p^{(2)} : p \in \delta(q, x)\}.

Konstruktionsidee (optional):
Die Idee hinter der Konstruktion ist, dass der ϵ\epsilon-NFA M′M' den NFA MM simuliert, aber genau zwei Nullen überspringen muss. Die Zustände von M′M' haben die Form q(i)q^{(i)}, wobei qq ein Zustand von MM ist und i∈{0,1,2}i \in \{0, 1, 2\} angibt, wie viele Nullen bereits übersprungen wurden. 

Wenn M′M' in einem Zustand q(i)q^{(i)} mit i<2i < 2 ist, kann er entweder ein Symbol normal verarbeiten (gemäß den Transitionen von MM) oder eine Null überspringen (mittels einer ϵ\epsilon-Transition, die den Zustand zu q(i+1)q^{(i+1)} übergehen lässt, wobei alle möglichen Zustände berücksichtigt werden, die MM beim Lesen einer Null erreichen würde).

Wenn M′M' in einem Zustand q(2)q^{(2)} ist, hat er bereits zwei Nullen übersprungen und verarbeitet die restlichen Symbole normal gemäß den Transitionen von MM.

Ein Wort ww wird von M′M' akzeptiert, wenn MM das Wort u0v0wu0v0w für einige u,v∈Σ∗u, v \in \Sigma^* akzeptieren würde, was genau der Definition von L↓0L^{\downarrow 0} entspricht.

Ihr Konstruktionsergebnis für M1M_1:
Zustände: q1^(0), q1^(1), q1^(2), q2^(0), q2^(1), q2^(2), q3^(0), q3^(1), q3^(2)
Startzustand: q1^(0)
Finalzustände: q3^(2)

Transitionen:
q1^(0) --0--> q2^(0)
q1^(0) --ε--> q2^(1)
q2^(0) --1--> q1^(0), q3^(0)
q2^(0) --0--> q3^(0)
q2^(0) --ε--> q3^(1)
q3^(0) --1--> q2^(0)

q1^(1) --0--> q2^(1)
q1^(1) --ε--> q2^(2)
q2^(1) --1--> q1^(1), q3^(1)
q2^(1) --0--> q3^(1)
q2^(1) --ε--> q3^(2)
q3^(1) --1--> q2^(1)

q1^(2) --0--> q2^(2)
q2^(2) --1--> q1^(2), q3^(2)
q2^(2) --0--> q3^(2)
q3^(2) --1--> q2^(2)

Subproblem c (0.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
wrong answer for choice (0)
The statement is false. A counterexample is L={0,1}∗⋅{00}⋅{0,1}∗L = \{0,1\}^* \cdot \{00\} \cdot \{0,1\}^*, the language of all strings that contain "00" as a substring.

To show that L↑0=LL^{\uparrow 0} = L:

1. L⊆L↑0L \subseteq L^{\uparrow 0}: For any word w∈Lw \in L, we can write w=u00vw = u00v for some u,v∈Σ∗u, v \in \Sigma^*. Then w=u00v=u0ε0v∈L↑0w = u00v = u0\varepsilon 0v \in L^{\uparrow 0} (taking u′=uu' = u, v′=εv' = \varepsilon, w′=vw' = v).

2. L↑0⊆LL^{\uparrow 0} \subseteq L: For any word w∈L↑0w \in L^{\uparrow 0}, we have w=u0v0w′w = u0v0w' for some u,v,w′∈Σ∗u, v, w' \in \Sigma^* such that uvw′∈Luvw' \in L. Since uvw′∈Luvw' \in L, we have uvw′=x00yuvw' = x00y for some x,y∈Σ∗x, y \in \Sigma^*. Then w=u0v0w′=u0v0x00yw = u0v0w' = u0v0x00y, which contains "00" as a substring. So w∈Lw \in L.

Since LL is non-empty (for example, 00∈L00 \in L) and L↑0=LL^{\uparrow 0} = L, this is a valid counterexample to the statement.