anthropic/claude-opus-4.1

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (6.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a∣0a∣a0\Null(a) := a \mid 0a \mid a0
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2∣r1Null(r2)∣r10r2\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2) \mid r_1 0 r_2
Null(r∗):=r∗0r∗∣r∗Null(r)r∗\Null(r^*) := r^* 0 r^* \mid r^* \Null(r) r^*

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall $r=r_1r_2$:
- **(IH1):** Für alle $u1v \in L(r_1)$ mit $u,v \in \Sigma^*$ gilt $u \in L(\Cut(r_1))$.
- **(IH2):** Für alle $u1v \in L(r_2)$ mit $u,v \in \Sigma^*$ gilt $u \in L(\Cut(r_2))$.

Beweis des Falls $r=r_1r_2$:
Sei $u1v \in L(r_1r_2)$ mit $u,v \in \Sigma^*$ beliebig gewählt. Da $u1v \in L(r_1r_2)$, existieren Wörter $w_1 \in L(r_1)$ und $w_2 \in L(r_2)$ mit $u1v = w_1w_2$.

Wir unterscheiden zwei Fälle, je nachdem wo die '1' in der Konkatenation $w_1w_2$ auftritt:

**Fall 1:** Die '1' befindet sich innerhalb von $w_1$ (d.h. $|u| + 1 \leq |w_1|$).
Dann können wir $w_1 = u1v'$ für ein $v' \in \Sigma^*$ schreiben, wobei $v = v'w_2$.
Da $u1v' = w_1 \in L(r_1)$, folgt aus **(IH1)**, dass $u \in L(\Cut(r_1))$.
Da $\Cut(r_1r_2) = \Cut(r_1) \mid r_1\Cut(r_2)$, gilt $u \in L(\Cut(r_1r_2))$.

**Fall 2:** Die '1' befindet sich innerhalb von $w_2$ (d.h. $|u| + 1 > |w_1|$).
Sei $u_2$ das Präfix von $w_2$ der Länge $|u| - |w_1|$, sodass $u = w_1u_2$.
Dann gilt $w_2 = u_21v_2$ für ein $v_2 \in \Sigma^*$ mit $v = v_2$.
Da $u_21v_2 = w_2 \in L(r_2)$, folgt aus **(IH2)**, dass $u_2 \in L(\Cut(r_2))$.
Daher gilt $u = w_1u_2 \in L(r_1\Cut(r_2))$.
Da $\Cut(r_1r_2) = \Cut(r_1) \mid r_1\Cut(r_2)$, gilt $u \in L(\Cut(r_1r_2))$.

In beiden Fällen haben wir gezeigt, dass $u \in L(\Cut(r_1r_2))$.

anthropic/claude-sonnet-4

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (5.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a∣0a∣a0\Null(a) := a \mid 0a \mid a0
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2∣r10r2∣r1Null(r2)\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 0 r_2 \mid r_1 \Null(r_2)
Null(r∗):=r∗(Null(r)∣0)r∗\Null(r^*) := r^* (\Null(r) \mid 0) r^*

Subproblem c (3.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
- Für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r1)u1v\in L(r_1) gilt u∈L(Cut(r1))u\in L(\Cut(r_1)) (IH für r1r_1)
- Für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r2)u1v\in L(r_2) gilt u∈L(Cut(r2))u\in L(\Cut(r_2)) (IH für r2r_2)

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^*. 

Da u1v∈L(r1r2)u1v\in L(r_1r_2), existieren w1∈L(r1)w_1\in L(r_1) und w2∈L(r2)w_2\in L(r_2) mit u1v=w1w2u1v = w_1w_2.

Wir betrachten zwei Fälle:

Fall 1: Die „1" liegt in w1w_1.
Dann ist w1=u1xw_1 = u1x für ein x∈Σ∗x\in\Sigma^* und w2=yvw_2 = yv für ein y∈Σ∗y\in\Sigma^* mit xy=εxy = \varepsilon (da w1w2=u1vw_1w_2 = u1v).
Also x=y=εx = y = \varepsilon, somit w1=u1w_1 = u1 und w2=vw_2 = v.

Da w1=u1∈L(r1)w_1 = u1\in L(r_1), folgt mit der Induktionshypothese für r1r_1 (angewandt auf u,εu,\varepsilon), dass u∈L(Cut(r1))u\in L(\Cut(r_1)).

Daher u∈L(Cut(r1))⊆L(Cut(r1)∣r1Cut(r2))=L(Cut(r1r2))u\in L(\Cut(r_1)) \subseteq L(\Cut(r_1) \mid r_1\Cut(r_2)) = L(\Cut(r_1r_2)).

Fall 2: Die „1" liegt in w2w_2.
Dann ist w1=uw_1 = u und w2=1vw_2 = 1v.

Da w2=1v∈L(r2)w_2 = 1v\in L(r_2), folgt mit der Induktionshypothese für r2r_2 (angewandt auf ε,v\varepsilon,v), dass ε∈L(Cut(r2))\varepsilon\in L(\Cut(r_2)).

Da w1=u∈L(r1)w_1 = u\in L(r_1) und ε∈L(Cut(r2))\varepsilon\in L(\Cut(r_2)), folgt u∈L(r1Cut(r2))u\in L(r_1\Cut(r_2)).

Daher u∈L(r1Cut(r2))⊆L(Cut(r1)∣r1Cut(r2))=L(Cut(r1r2))u\in L(r_1\Cut(r_2)) \subseteq L(\Cut(r_1) \mid r_1\Cut(r_2)) = L(\Cut(r_1r_2)).

In beiden Fällen gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).

deepseek/deepseek-chat-v3.1

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (5.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a∣0a∣a0\Null(a) := a \mid 0a \mid a0
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2∣r1Null(r2)∣r10r2\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2) \mid r_1 0 r_2
Null(r∗):=ϵ∣0∣Null(r)r∗∣r0r∗∣rNull(r∗)\Null(r^*) := \epsilon \mid 0 \mid \Null(r) r^* \mid r 0 r^* \mid r \Null(r^*)

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
- Für r1r_1: Für alle u,v∈Σ∗u,v \in \Sigma^* mit u1v∈L(r1)u1v \in L(r_1) gilt u∈L(Cut(r1))u \in L(\Cut(r_1)).
- Für r2r_2: Für alle u,v∈Σ∗u,v \in \Sigma^* mit u1v∈L(r2)u1v \in L(r_2) gilt u∈L(Cut(r2))u \in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Seien u,v∈Σ∗u,v \in \Sigma^* mit u1v∈L(r1r2)u1v \in L(r_1 r_2). Da L(r1r2)=L(r1)L(r2)L(r_1 r_2) = L(r_1) L(r_2), existieren x∈L(r1)x \in L(r_1) und y∈L(r2)y \in L(r_2) mit u1v=xyu1v = xy.

Wir unterscheiden zwei Fälle basierend auf der Position des '1' in xyxy:

1. Fall: Das '1' ist in xx enthalten.  
   Das heißt, es existiert ein v′∈Σ∗v' \in \Sigma^* such that x=u1v′x = u1v' und y=vy = v (da u1v=(u1v′)yu1v = (u1v')y implies v′y=vv' y = v, but for the prefix, we have x=u1v′x = u1v' for some v′v').  
   Da x=u1v′∈L(r1)x = u1v' \in L(r_1), folgt aus der Induktionshypothese für r1r_1, dass u∈L(Cut(r1))u \in L(\Cut(r_1)).  
   Nach Definition ist Cut(r1r2)=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) = \Cut(r_1) \mid r_1 \Cut(r_2), also L(Cut(r1r2))=L(Cut(r1))∪L(r1Cut(r2))L(\Cut(r_1 r_2)) = L(\Cut(r_1)) \cup L(r_1 \Cut(r_2)).  
   Da u∈L(Cut(r1))u \in L(\Cut(r_1)), folgt u∈L(Cut(r1r2))u \in L(\Cut(r_1 r_2)).

2. Fall: Das '1' ist in yy enthalten.  
   Das heißt, es existieren u′∈Σ∗u' \in \Sigma^* und v′∈Σ∗v' \in \Sigma^* such that y=u′1v′y = u'1v' und xu′=ux u' = u (da u1v=x(u′1v′)u1v = x(u'1v') implies u=xu′u = x u' und v=v′v = v').  
   Da y=u′1v′∈L(r2)y = u'1v' \in L(r_2), folgt aus der Induktionshypothese für r2r_2, dass u′∈L(Cut(r2))u' \in L(\Cut(r_2)).  
   Da x∈L(r1)x \in L(r_1) und u′∈L(Cut(r2))u' \in L(\Cut(r_2)), ist xu′∈L(r1Cut(r2))x u' \in L(r_1 \Cut(r_2)).  
   Nach Definition ist Cut(r1r2)=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) = \Cut(r_1) \mid r_1 \Cut(r_2), also L(Cut(r1r2))=L(Cut(r1))∪L(r1Cut(r2))L(\Cut(r_1 r_2)) = L(\Cut(r_1)) \cup L(r_1 \Cut(r_2)).  
   Da u=xu′∈L(r1Cut(r2))u = x u' \in L(r_1 \Cut(r_2)), folgt u∈L(Cut(r1r2))u \in L(\Cut(r_1 r_2)).

In beiden Fällen gilt u∈L(Cut(r1r2))u \in L(\Cut(r_1 r_2)), was zu zeigen war.

deepseek/deepseek-r1-0528

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (6.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=0a∣a0∣a\Null(a) := 0a \mid a0 \mid a
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)⋅r2∣r1⋅0⋅r2∣r1⋅Null(r2)\Null(r_1 r_2) := \Null(r_1) \cdot r_2 \mid r_1 \cdot 0 \cdot r_2 \mid r_1 \cdot \Null(r_2)
Null(r∗):=r∗∣r∗⋅Null(r)⋅r∗∣r∗⋅0⋅r∗\Null(r^*) := r^* \mid r^* \cdot \Null(r) \cdot r^* \mid r^* \cdot 0 \cdot r^*

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
- Für r1r_1: Für alle u,v∈Σ∗u, v \in \Sigma^* mit u1v∈L(r1)u1v \in L(r_1) gilt u∈L(Cut(r1))u \in L(\text{Cut}(r_1)).
- Für r2r_2: Für alle u,v∈Σ∗u, v \in \Sigma^* mit u1v∈L(r2)u1v \in L(r_2) gilt u∈L(Cut(r2))u \in L(\text{Cut}(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1v∈L(r1r2)u1v \in L(r_1 r_2). Dann existieren w1∈L(r1)w_1 \in L(r_1) und w2∈L(r2)w_2 \in L(r_2) mit u1v=w1w2u1v = w_1 w_2.

1. Fall 1: Das '1' liegt in w1w_1.
   - Dann ist w1=u′1v′w_1 = u'1v' für geeignete u′,v′∈Σ∗u', v' \in \Sigma^* mit u=u′u = u' und v′w2=vv' w_2 = v.
   - Da w1=u′1v′∈L(r1)w_1 = u'1v' \in L(r_1), folgt aus der Induktionshypothese für r1r_1, dass u′∈L(Cut(r1))u' \in L(\text{Cut}(r_1)).
   - Weil Cut(r1r2)=Cut(r1)∣r1Cut(r2)\text{Cut}(r_1 r_2) = \text{Cut}(r_1) \mid r_1 \text{Cut}(r_2), ist L(Cut(r1))⊆L(Cut(r1r2))L(\text{Cut}(r_1)) \subseteq L(\text{Cut}(r_1 r_2)).
   - Also: u=u′∈L(Cut(r1r2))u = u' \in L(\text{Cut}(r_1 r_2)).

2. Fall 2: Das '1' liegt in w2w_2.
   - Dann ist w2=u′′1v′′w_2 = u''1v'' für geeignete u′′,v′′∈Σ∗u'', v'' \in \Sigma^* mit u=w1u′′u = w_1 u'' und v′′=vv'' = v.
   - Da w2=u′′1v′′∈L(r2)w_2 = u''1v'' \in L(r_2), folgt aus der Induktionshypothese für r2r_2, dass u′′∈L(Cut(r2))u'' \in L(\text{Cut}(r_2)).
   - Dann ist w1u′′∈L(r1Cut(r2))w_1 u'' \in L(r_1 \text{Cut}(r_2)), da w1∈L(r1)w_1 \in L(r_1) und u′′∈L(Cut(r2))u'' \in L(\text{Cut}(r_2)).
   - Weil Cut(r1r2)=Cut(r1)∣r1Cut(r2)\text{Cut}(r_1 r_2) = \text{Cut}(r_1) \mid r_1 \text{Cut}(r_2), ist L(r1Cut(r2))⊆L(Cut(r1r2))L(r_1 \text{Cut}(r_2)) \subseteq L(\text{Cut}(r_1 r_2)).
   - Also: u=w1u′′∈L(Cut(r1r2))u = w_1 u'' \in L(\text{Cut}(r_1 r_2)).

google/gemini-2.5-pro

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (6.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a∣0a∣a0\Null(a) := a \mid 0a \mid a0
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2∣r1Null(r2)\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2)
Null(r∗):=(ϵ∣0)∣r∗Null(r)r∗\Null(r^*) := (\epsilon \mid 0) \mid r^* \Null(r) r^*

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
Die Eigenschaft gilt für die direkten Teil-Ausdrücke r1r_1 und r2r_2.
(IH1): Für alle u′,v′∈Σ∗u',v'\in\Sigma^* mit u′1v′∈L(r1)u'1v'\in L(r_1) gilt u′∈L(Cut(r1))u'\in L(\Cut(r_1)).
(IH2): Für alle u′′,v′′∈Σ∗u'',v''\in\Sigma^* mit u′′1v′′∈L(r2)u''1v''\in L(r_2) gilt u′′∈L(Cut(r2))u''\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1v∈L(r1r2)u1v \in L(r_1r_2) für beliebige u,v∈Σ∗u,v\in\Sigma^*.
Per Definition von L(r1r2)L(r_1r_2) gibt es Wörter w1∈L(r1)w_1\in L(r_1) und w2∈L(r2)w_2\in L(r_2), sodass u1v=w1w2u1v = w_1w_2.
Das Zeichen '1' muss entweder in w1w_1 oder in w2w_2 vorkommen. Wir betrachten beide Fälle.

Fall 1: Das Zeichen '1' kommt in w1w_1 vor.
Dann kann man w1w_1 als w1=u′1v′w_1=u'1v' für gewisse u′,v′∈Σ∗u',v'\in\Sigma^* schreiben.
Das gesamte Wort ist also u1v=(u′1v′)w2u1v = (u'1v')w_2.
Daraus folgt, dass u=u′u=u' sein muss.
Da w1=u′1v′∈L(r1)w_1 = u'1v'\in L(r_1) gilt, können wir die Induktionshypothese (IH1) anwenden und erhalten u′∈L(Cut(r1))u' \in L(\Cut(r_1)).
Weil u=u′u=u', folgt u∈L(Cut(r1))u \in L(\Cut(r_1)).
Per Definition ist Cut(r1r2)=Cut(r1)∣r1Cut(r2)\Cut(r_1r_2) = \Cut(r_1) \mid r_1\Cut(r_2).
Da u∈L(Cut(r1))u \in L(\Cut(r_1)), gilt auch u∈L(Cut(r1)∣r1Cut(r2))u \in L(\Cut(r_1) \mid r_1\Cut(r_2)), und somit u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).

Fall 2: Das Zeichen '1' kommt in w2w_2 vor.
Dann kann man w2w_2 als w2=u′′1v′′w_2=u''1v'' für gewisse u′′,v′′∈Σ∗u'',v''\in\Sigma^* schreiben.
Das gesamte Wort ist also u1v=w1(u′′1v′′)u1v = w_1(u''1v'').
Daraus folgt, dass u=w1u′′u=w_1u'' sein muss.
Da w2=u′′1v′′∈L(r2)w_2 = u''1v''\in L(r_2) gilt, können wir die Induktionshypothese (IH2) anwenden und erhalten u′′∈L(Cut(r2))u'' \in L(\Cut(r_2)).
Wir wissen w1∈L(r1)w_1\in L(r_1) und u′′∈L(Cut(r2))u''\in L(\Cut(r_2)).
Also ist das Wort u=w1u′′u=w_1u'' in der Sprache L(r1)L(Cut(r2))=L(r1Cut(r2))L(r_1)L(\Cut(r_2)) = L(r_1\Cut(r_2)).
Per Definition ist Cut(r1r2)=Cut(r1)∣r1Cut(r2)\Cut(r_1r_2) = \Cut(r_1) \mid r_1\Cut(r_2).
Da u∈L(r1Cut(r2))u \in L(r_1\Cut(r_2)), gilt auch u∈L(Cut(r1)∣r1Cut(r2))u \in L(\Cut(r_1) \mid r_1\Cut(r_2)), und somit u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).

In beiden Fällen haben wir gezeigt, dass u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)). Somit ist der Induktionsschritt für r=r1r2r=r_1r_2 bewiesen.

openai/gpt-5

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0,00,01,001,010\}

Subproblem b (5.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a∣0a∣a0\Null(a) := a \mid 0a \mid a0
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1) r2∣r1 Null(r2)\Null(r_1 r_2) := \Null(r_1)\, r_2 \mid r_1\, \Null(r_2)
Null(r∗):=r∗ Null(r) r∗\Null(r^*) := r^*\, \Null(r)\, r^*

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
IH1_1: Für alle u′,v′∈Σ∗u',v'\in\Sigma^* gilt: Wenn u′1v′∈L(r1)u'1v'\in L(r_1), dann u′∈L(Cut(r1))u'\in L(\Cut(r_1)).
IH2_2: Für alle u′,v′∈Σ∗u',v'\in\Sigma^* gilt: Wenn u′1v′∈L(r2)u'1v'\in L(r_2), dann u′∈L(Cut(r2))u'\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Seien u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r1r2)u1v\in L(r_1r_2). Dann gibt es x∈L(r1)x\in L(r_1) und y∈L(r2)y\in L(r_2) mit u1v=xyu1v=xy.
Betrachte die Lage des ausgezeichneten Zeichens 11 relativ zur Zerlegung xyxy.

Fall 1: 11 liegt in xx. Dann existiert t∈Σ∗t\in\Sigma^* mit x=u1tx=u1t. Also u1t∈L(r1)u1t\in L(r_1). Nach IH1_1 (Anwendung der IH1_1) folgt u∈L(Cut(r1))u\in L(\Cut(r_1)). Damit u∈L(Cut(r1)∣r1Cut(r2))=L(Cut(r1r2))u\in L(\Cut(r_1)\mid r_1\Cut(r_2))=L(\Cut(r_1r_2)) (per Definition von Cut\Cut).

Fall 2: 11 liegt in yy. Dann existieren p,q∈Σ∗p,q\in\Sigma^* mit y=p1qy=p1q und u=xpu=xp. Da p1q∈L(r2)p1q\in L(r_2), liefert IH2_2 (Anwendung der IH2_2) p∈L(Cut(r2))p\in L(\Cut(r_2)). Mit x∈L(r1)x\in L(r_1) folgt u=xp∈L(r1Cut(r2))u=xp\in L(r_1\Cut(r_2)). Also u∈L(Cut(r1)∣r1Cut(r2))=L(Cut(r1r2))u\in L(\Cut(r_1)\mid r_1\Cut(r_2))=L(\Cut(r_1r_2)).

In beiden Fällen gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)). Damit ist der Fall r=r1r2r=r_1r_2 gezeigt.

openai/gpt-oss-120b

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,010,001}N(\{01, 0\})=\{0,00,01,010,001\}

Subproblem b (5.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a∣0a∣a0\Null(a) := a \mid 0a \mid a0
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1) r2∣r1 Null(r2)\Null(r_1 r_2) := \Null(r_1)\, r_2 \mid r_1\, \Null(r_2)
Null(r∗):=(r∗) Null(r) (r∗)\Null(r^*) := (r^{*})\, \Null(r)\, (r^{*})

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
**Induktionshypothese(n) für den Fall \(r = r_{1}r_{2}\):**  

1. *(IH 1)* Für alle \(u_{1}v\in L(r_{1})\) mit \(u_{1},v\in\Sigma^{*}\) gilt  
   \(\displaystyle u_{1}\in L(\Cut(r_{1})).\)

2. *(IH 2)* Für alle \(u_{2}v\in L(r_{2})\) mit \(u_{2},v\in\Sigma^{*}\) gilt  
   \(\displaystyle u_{2}\in L(\Cut(r_{2})).\)

---

**Beweis des Falls \(r = r_{1}r_{2}\):**  

Sei \(u1v\in L(r_{1}r_{2})\) mit \(u,v\in\Sigma^{*}\).  
Nach der Definition der Konkatenation gibt es Wörter \(x\in L(r_{1})\) und \(y\in L(r_{2})\) derart, dass  

\[
u1v = xy .
\]

Der einzelne Buchstabe \(1\) befindet sich entweder in \(x\) **oder** in \(y\). Wir behandeln beide Möglichkeiten getrennt.

---

**Fall 1 – die 1 liegt in \(x\).**  

Dann lässt sich \(x\) schreiben als \(x = u_{1}1v_{1}\) mit \(u_{1},v_{1}\in\Sigma^{*}\) und \(y\) beliebig.  
Da \(x\in L(r_{1})\) und \(u_{1}1v_{1}\in L(r_{1})\), dürfen wir die Induktionshypothese **(IH 1)** anwenden und erhalten  

\[
u_{1}\in L(\Cut(r_{1})).
\]

Weil nach Definition  

\[
\Cut(r_{1}r_{2}) = \Cut(r_{1}) \mid r_{1}\Cut(r_{2}),
\]

ist jedes Wort aus \(L(\Cut(r_{1}))\) zugleich ein Wort aus \(L(\Cut(r_{1}r_{2}))\). Also  

\[
u = u_{1}\in L(\Cut(r_{1}r_{2})).
\]

---

**Fall 2 – die 1 liegt in \(y\).**  

Dann hat \(y\) die Form \(y = u_{2}1v_{2}\) mit \(u_{2},v_{2}\in\Sigma^{*}\) und \(x\) enthält kein 1.  
Wir haben also  

\[
x\in L(r_{1}) \quad\text{und}\quad u_{2}1v_{2}\in L(r_{2}).
\]

Aus \(u_{2}1v_{2}\in L(r_{2})\) und **(IH 2)** folgt  

\[
u_{2}\in L(\Cut(r_{2})).
\]

Damit ist das Wort \(xu_{2}\) ein Element von  

\[
L(r_{1})\,L(\Cut(r_{2})) \subseteq L(\Cut(r_{1}) \mid r_{1}\Cut(r_{2}))
      = L(\Cut(r_{1}r_{2})).
\]

Da das ursprüngliche Präfix vor dem Symbol \(1\) genau \(u = xu_{2}\) ist, erhalten wir  

\[
u\in L(\Cut(r_{1}r_{2})).
\]

---

In beiden Fällen folgt aus der Annahme \(u1v\in L(r_{1}r_{2})\), dass \(u\in L(\Cut(r_{1}r_{2}))\). Damit ist die zu zeigende Aussage für den Fall \(r = r_{1}r_{2}\) bewiesen. ∎

qwen/qwen3-235b-a22b

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (5.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset  
Null(ϵ):=ϵ+0\Null(\epsilon) := \epsilon + 0  
Null(a):=a+0a+a0\Null(a) := a + 0a + a0  
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)  
Null(r1r2):=Null(r1)r2∣r1Null(r2)∣r10r2\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2) \mid r_1 0 r_2  
Null(r∗):=r∗∣r∗0r∗\Null(r^*) := r^* \mid r^* 0 r^*

Subproblem c (5.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:  
IH₁: Für alle u′,v′∈Σ∗u',v'\in\Sigma^* mit u′1v′∈L(r1)u'1v'\in L(r_1) gilt u′∈L(Cut(r1))u'\in L(\Cut(r_1)).  
IH₂: Für alle u′′,v′′∈Σ∗u'',v''\in\Sigma^* mit u′′1v′′∈L(r2)u''1v''\in L(r_2) gilt u′′∈L(Cut(r2))u''\in L(\Cut(r_2)).  

Beweis des Falls r=r1r2r=r_1r_2:  
Null(∅):=∅\Null(\emptyset) := \emptyset  
Sei u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^*. Dann gibt es x∈L(r1)x\in L(r_1), y∈L(r2)y\in L(r_2) mit u1v=xyu1v=xy. Infolgedessen gibt es zwei Fälle:  

Fall 1: Der erste Buchstabe 11 in xyxy liegt in xx. Dann ist xx von der Form x=u′1v′x=u'1v', so dass u′1v′∈L(r1)u'1v' \in L(r_1) und u=u′u=u' gilt. Nach IH₁ folgt u′=u∈L(Cut(r1))u'=u\in L(\Cut(r_1)), also u∈L(Cut(r1)∣r1Cut(r2))=L(Cut(r1r2))u\in L(\Cut(r_1)|r_1\Cut(r_2)) = L(\Cut(r_1r_2)).  

Fall 2: Der erste Buchstabe 11 in xyxy liegt in yy. Dann ist xx ein Präsifix von u1vu1v, welches zu L(r1)L(r_1) gehört, und y=u′′1v′′y=u''1v'' mit u′′1v′′∈L(r2)u''1v''\in L(r_2) und u=xu′′u=xu''. Nach IH₂ folgt u′′∈L(Cut(r2))u''\in L(\Cut(r_2)), also xu′′∈L(r1Cut(r2))⊆L(Cut(r1r2))xu''\in L(r_1\Cut(r_2))\subseteq L(\Cut(r_1r_2)). Da u=xu′′u=xu'', gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).  

Insbesondere erfüllt x=u′∈L(r1)x=u' \in L(r_1) (Fall 1) bzw. xu′′∈L(r1)⋅L(Cut(r2))xu'' \in L(r_1)\cdot L(\Cut(r_2)) (Fall 2) die Behauptung.

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

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (5.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a∣(0a)∣(a0)\Null(a) := a \mid (0a) \mid (a0)
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2∣r1Null(r2)\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2)
Null(r∗):=r∗Null(r)r∗\Null(r^*) := r^* \Null(r) r^*

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
Wir nehmen an, dass die Aussage für r1r_1 und r2r_2 gilt, also:
- Für alle u1,v1∈Σ∗u_1,v_1\in\Sigma^* mit u11v1∈L(r1)u_1 1 v_1\in L(r_1) gilt u1∈L(Cut(r1))u_1\in L(\Cut(r_1)).
- Für alle u2,v2∈Σ∗u_2,v_2\in\Sigma^* mit u21v2∈L(r2)u_2 1 v_2\in L(r_2) gilt u2∈L(Cut(r2))u_2\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1v∈L(r1r2)u 1 v \in L(r_1 r_2) mit u,v∈Σ∗u, v \in \Sigma^*. Dann gibt es w1,w2w_1, w_2 mit w1w2=u1vw_1 w_2 = u 1 v, w1∈L(r1)w_1 \in L(r_1), w2∈L(r2)w_2 \in L(r_2).

Wir unterscheiden zwei Fälle:
- Fall 1: Der Buchstabe "1" liegt in w1w_1, d.h. w1=u11v1w_1 = u_1 1 v_1 für einige u1,v1∈Σ∗u_1, v_1 \in \Sigma^*, und u=u1u = u_1, v1w2=1vv_1 w_2 = 1 v.
  Dann ist u11v1∈L(r1)u_1 1 v_1 \in L(r_1). Nach Induktionshypothese für r1r_1 folgt u1∈L(Cut(r1))u_1 \in L(\Cut(r_1)) (IH1). 
  Da Cut(r1r2)=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) = \Cut(r_1) \mid r_1 \Cut(r_2), ist u=u1∈L(Cut(r1))⊆L(Cut(r1r2))u = u_1 \in L(\Cut(r_1)) \subseteq L(\Cut(r_1 r_2)).

- Fall 2: Der Buchstabe "1" liegt in w2w_2, d.h. w2=u21v2w_2 = u_2 1 v_2 für einige u2,v2∈Σ∗u_2, v_2 \in \Sigma^*, und u=w1u2u = w_1 u_2, v2=vv_2 = v.
  Dann ist u21v2∈L(r2)u_2 1 v_2 \in L(r_2). Nach Induktionshypothese für r2r_2 folgt u2∈L(Cut(r2))u_2 \in L(\Cut(r_2)) (IH2).
  Da w1∈L(r1)w_1 \in L(r_1) und u2∈L(Cut(r2))u_2 \in L(\Cut(r_2)), ist w1u2∈L(r1Cut(r2))w_1 u_2 \in L(r_1 \Cut(r_2)).
  Da Cut(r1r2)=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) = \Cut(r_1) \mid r_1 \Cut(r_2), ist u=w1u2∈L(r1Cut(r2))⊆L(Cut(r1r2))u = w_1 u_2 \in L(r_1 \Cut(r_2)) \subseteq L(\Cut(r_1 r_2)).

In beiden Fällen gilt u∈L(Cut(r1r2))u \in L(\Cut(r_1 r_2)), was zu zeigen war.

x-ai/grok-4

Exercise 3: Rekursive Funktionen

Sei Σ:={0,1}\Sigma:=\{0,1\}. Für eine Sprache L⊆Σ∗L\subseteq\Sigma^* bezeichnet N(L)N(L) die Sprache, die man erhält, wenn man den Wörtern aus LL höchstens eine Null an einer beliebigen Stelle hinzufügt. Formal definieren wir
N(L):={vxw∣v,w∈Σ∗∧x∈{0,ε}∧vw∈L}N(L):= \{vxw \mid v,w\in \Sigma^*\wedge x\in \{0,\varepsilon\}\wedge vw\in L\}

Subproblem a (1.0/1.0P)

Listen Sie alle Wörter der Sprache N({01,0})N(\{01, 0\}) explizit auf:
N({01,0})={0,00,01,001,010}N(\{01, 0\})=\{0, 00, 01, 001, 010\}

Subproblem b (6.0/6.0P)

Geben Sie eine rekursive Funktion Null\Null an, sodass Null(r)\Null(r) ein regulärer Ausdruck mit L(Null(r))=N(L(r))L(\Null(r)) = N(L(r)) ist, für jeden regulären Ausdruck rr. Im Folgenden sind r,r1,r2r,r_1,r_2 reguläre Ausdrücke, und a∈Σa\in \Sigma.
Null(∅):=∅\Null(\emptyset) := \emptyset
Null(ϵ):=ϵ∣0\Null(\epsilon) := \epsilon \mid 0
Null(a):=a∣0 a∣a 0\Null(a) := a \mid 0\,a \mid a\,0
Null(r1∣r2):=Null(r1)∣Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2∣r1Null(r2)\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2)
Null(r∗):=r∗((ϵ∣0)∣Null(r)r∗)\Null(r^*) := r^* ((\epsilon \mid 0) \mid \Null(r) r^*)

Subproblem c (6.0/6.0P)

Gegeben sei die folgende rekursive Funktion über dem Alphabet Σ:={0,1}\Sigma:=\{0,1\}:
Cut(∅):=∅\Cut(\emptyset) := \emptyset
Cut(0):=∅\Cut(0) := \emptyset
Cut(r1∣r2):=Cut(r1)∣Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r∗):=r∗Cut(r)\Cut(r^*) := r^*\Cut(r)
Cut(ϵ):=∅\Cut(\epsilon) := \emptyset
Cut(1):=ϵ\Cut(1) := \epsilon
Cut(r1r2):=Cut(r1)∣r1Cut(r2)\Cut(r_1 r_2) := \Cut(r_1)\mid r_1\Cut(r_2)

Per struktureller Induktion über rr lässt sich zeigen, dass für alle u,v∈Σ∗u,v\in\Sigma^* mit u1v∈L(r)u1v\in L(r) gilt, dass u∈L(Cut(r))u\in L(\Cut(r)).

Vervollständigen Sie den Beweis für den Fall r=r1r2r=r_1r_2. Ergänzen Sie die Induktionshypothese(n) und führen Sie dann den Beweis. Kennzeichnen Sie Verwendungen der Induktionshypothesen im Beweis deutlich.

Zu zeigen: Für alle u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^* gilt u∈L(Cut(r1r2))u\in L(\Cut(r_1r_2)).
Induktionshypothese(n) für den Fall r=r1r2r=r_1r_2:
Die Aussage gilt für r1r_1 und r2r_2. Das heißt:

(IH1) Für alle u′,v′∈Σ∗u',v'\in\Sigma^* mit u′1v′∈L(r1)u'1v'\in L(r_1) gilt u′∈L(Cut(r1))u'\in L(\Cut(r_1)).

(IH2) Für alle u′,v′∈Σ∗u',v'\in\Sigma^* mit u′1v′∈L(r2)u'1v'\in L(r_2) gilt u′∈L(Cut(r2))u'\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1v∈L(r1r2)u1v\in L(r_1r_2) mit u,v∈Σ∗u,v\in\Sigma^*. Dann existieren x∈L(r1)x\in L(r_1), y∈L(r2)y\in L(r_2) mit xy=u1vxy = u1v. Sei k:=∣x∣k:=|x| und m:=∣u∣+1m:=|u|+1 (Position des '1' in u1vu1v).

Fall 1: k≥mk\geq m.  
Dann liegt das '1' in xx, also x=u1x′′x = u 1 x'' für ein x′′∈Σ∗x''\in\Sigma^* (mit ∣x′′∣=k−m|x''| = k-m). Somit ist u1x′′∈L(r1)u1x''\in L(r_1).  
Nach (IH1) gilt u∈L(Cut(r1))⊆L(Cut(r1r2))u\in L(\Cut(r_1))\subseteq L(\Cut(r_1r_2)).

Fall 2: k<mk < m.  
Dann liegt das '1' in yy, also y=y′1y′′y = y' 1 y'' für y′,y′′∈Σ∗y',y''\in\Sigma^* mit ∣y′∣=m−k−1|y'|=m-k-1. Somit ist u=xy′u = x y' und v=y′′v = y''.  
Nach (IH2) gilt y′∈L(Cut(r2))y'\in L(\Cut(r_2)).  
Daher ist u=xy′∈L(r1)L(Cut(r2))⊆L(Cut(r1r2))u = x y'\in L(r_1)L(\Cut(r_2))\subseteq L(\Cut(r_1r_2)).