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):={vxwv,wΣx{0,ε}vwL}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):=a0aa0\Null(a) := a \mid 0a \mid a0
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r1Null(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):=r0rrNull(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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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):={vxwv,wΣx{0,ε}vwL}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):=a0aa0\Null(a) := a \mid 0a \mid a0
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r10r2r1Null(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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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 u1vL(r1)u1v\in L(r_1) gilt uL(Cut(r1))u\in L(\Cut(r_1)) (IH für r1r_1)
- Für alle u,vΣu,v\in\Sigma^* mit u1vL(r2)u1v\in L(r_2) gilt uL(Cut(r2))u\in L(\Cut(r_2)) (IH für r2r_2)

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

Da u1vL(r1r2)u1v\in L(r_1r_2), existieren w1L(r1)w_1\in L(r_1) und w2L(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=u1L(r1)w_1 = u1\in L(r_1), folgt mit der Induktionshypothese für r1r_1 (angewandt auf u,εu,\varepsilon), dass uL(Cut(r1))u\in L(\Cut(r_1)).

Daher uL(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=1vL(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=uL(r1)w_1 = u\in L(r_1) und εL(Cut(r2))\varepsilon\in L(\Cut(r_2)), folgt uL(r1Cut(r2))u\in L(r_1\Cut(r_2)).

Daher uL(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 uL(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):={vxwv,wΣx{0,ε}vwL}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):=a0aa0\Null(a) := a \mid 0a \mid a0
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r1Null(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):=ϵ0Null(r)rr0rrNull(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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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 u1vL(r1)u1v \in L(r_1) gilt uL(Cut(r1))u \in L(\Cut(r_1)).
- Für r2r_2: Für alle u,vΣu,v \in \Sigma^* mit u1vL(r2)u1v \in L(r_2) gilt uL(Cut(r2))u \in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Seien u,vΣu,v \in \Sigma^* mit u1vL(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 xL(r1)x \in L(r_1) und yL(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=u1vx = u1v' und y=vy = v (da u1v=(u1v)yu1v = (u1v')y implies vy=vv' y = v, but for the prefix, we have x=u1vx = u1v' for some vv').  
   Da x=u1vL(r1)x = u1v' \in L(r_1), folgt aus der Induktionshypothese für r1r_1, dass uL(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 uL(Cut(r1))u \in L(\Cut(r_1)), folgt uL(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=u1vy = u'1v' und xu=ux u' = u (da u1v=x(u1v)u1v = x(u'1v') implies u=xuu = x u' und v=vv = v').  
   Da y=u1vL(r2)y = u'1v' \in L(r_2), folgt aus der Induktionshypothese für r2r_2, dass uL(Cut(r2))u' \in L(\Cut(r_2)).  
   Da xL(r1)x \in L(r_1) und uL(Cut(r2))u' \in L(\Cut(r_2)), ist xuL(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=xuL(r1Cut(r2))u = x u' \in L(r_1 \Cut(r_2)), folgt uL(Cut(r1r2))u \in L(\Cut(r_1 r_2)).

In beiden Fällen gilt uL(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):={vxwv,wΣx{0,ε}vwL}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):=0aa0a\Null(a) := 0a \mid a0 \mid a
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r10r2r1Null(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):=rrNull(r)rr0r\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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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 u1vL(r1)u1v \in L(r_1) gilt uL(Cut(r1))u \in L(\text{Cut}(r_1)).
- Für r2r_2: Für alle u,vΣu, v \in \Sigma^* mit u1vL(r2)u1v \in L(r_2) gilt uL(Cut(r2))u \in L(\text{Cut}(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1vL(r1r2)u1v \in L(r_1 r_2). Dann existieren w1L(r1)w_1 \in L(r_1) und w2L(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=u1vw_1 = u'1v' für geeignete u,vΣu', v' \in \Sigma^* mit u=uu = u' und vw2=vv' w_2 = v.
   - Da w1=u1vL(r1)w_1 = u'1v' \in L(r_1), folgt aus der Induktionshypothese für r1r_1, dass uL(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=uL(Cut(r1r2))u = u' \in L(\text{Cut}(r_1 r_2)).

2. Fall 2: Das '1' liegt in w2w_2.
   - Dann ist w2=u1vw_2 = u''1v'' für geeignete u,vΣu'', v'' \in \Sigma^* mit u=w1uu = w_1 u'' und v=vv'' = v.
   - Da w2=u1vL(r2)w_2 = u''1v'' \in L(r_2), folgt aus der Induktionshypothese für r2r_2, dass uL(Cut(r2))u'' \in L(\text{Cut}(r_2)).
   - Dann ist w1uL(r1Cut(r2))w_1 u'' \in L(r_1 \text{Cut}(r_2)), da w1L(r1)w_1 \in L(r_1) und uL(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=w1uL(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):={vxwv,wΣx{0,ε}vwL}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):=a0aa0\Null(a) := a \mid 0a \mid a0
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r1Null(r2)\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2)
Null(r):=(ϵ0)rNull(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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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 u1vL(r1)u'1v'\in L(r_1) gilt uL(Cut(r1))u'\in L(\Cut(r_1)).
(IH2): Für alle u,vΣu'',v''\in\Sigma^* mit u1vL(r2)u''1v''\in L(r_2) gilt uL(Cut(r2))u''\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1vL(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 w1L(r1)w_1\in L(r_1) und w2L(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=u1vw_1=u'1v' für gewisse u,vΣu',v'\in\Sigma^* schreiben.
Das gesamte Wort ist also u1v=(u1v)w2u1v = (u'1v')w_2.
Daraus folgt, dass u=uu=u' sein muss.
Da w1=u1vL(r1)w_1 = u'1v'\in L(r_1) gilt, können wir die Induktionshypothese (IH1) anwenden und erhalten uL(Cut(r1))u' \in L(\Cut(r_1)).
Weil u=uu=u', folgt uL(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 uL(Cut(r1))u \in L(\Cut(r_1)), gilt auch uL(Cut(r1)r1Cut(r2))u \in L(\Cut(r_1) \mid r_1\Cut(r_2)), und somit uL(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=u1vw_2=u''1v'' für gewisse u,vΣu'',v''\in\Sigma^* schreiben.
Das gesamte Wort ist also u1v=w1(u1v)u1v = w_1(u''1v'').
Daraus folgt, dass u=w1uu=w_1u'' sein muss.
Da w2=u1vL(r2)w_2 = u''1v''\in L(r_2) gilt, können wir die Induktionshypothese (IH2) anwenden und erhalten uL(Cut(r2))u'' \in L(\Cut(r_2)).
Wir wissen w1L(r1)w_1\in L(r_1) und uL(Cut(r2))u''\in L(\Cut(r_2)).
Also ist das Wort u=w1uu=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 uL(r1Cut(r2))u \in L(r_1\Cut(r_2)), gilt auch uL(Cut(r1)r1Cut(r2))u \in L(\Cut(r_1) \mid r_1\Cut(r_2)), und somit uL(Cut(r1r2))u\in L(\Cut(r_1r_2)).

In beiden Fällen haben wir gezeigt, dass uL(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):={vxwv,wΣx{0,ε}vwL}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):=a0aa0\Null(a) := a \mid 0a \mid a0
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r1Null(r2)\Null(r_1 r_2) := \Null(r_1)\, r_2 \mid r_1\, \Null(r_2)
Null(r):=rNull(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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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 u1vL(r1)u'1v'\in L(r_1), dann uL(Cut(r1))u'\in L(\Cut(r_1)).
IH2_2: Für alle u,vΣu',v'\in\Sigma^* gilt: Wenn u1vL(r2)u'1v'\in L(r_2), dann uL(Cut(r2))u'\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Seien u,vΣu,v\in\Sigma^* mit u1vL(r1r2)u1v\in L(r_1r_2). Dann gibt es xL(r1)x\in L(r_1) und yL(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 u1tL(r1)u1t\in L(r_1). Nach IH1_1 (Anwendung der IH1_1) folgt uL(Cut(r1))u\in L(\Cut(r_1)). Damit uL(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 p1qL(r2)p1q\in L(r_2), liefert IH2_2 (Anwendung der IH2_2) pL(Cut(r2))p\in L(\Cut(r_2)). Mit xL(r1)x\in L(r_1) folgt u=xpL(r1Cut(r2))u=xp\in L(r_1\Cut(r_2)). Also uL(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 uL(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):={vxwv,wΣx{0,ε}vwL}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):=a0aa0\Null(a) := a \mid 0a \mid a0
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r1Null(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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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):={vxwv,wΣx{0,ε}vwL}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(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)  
Null(r1r2):=Null(r1)r2r1Null(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):=rr0r\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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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 u1vL(r1)u'1v'\in L(r_1) gilt uL(Cut(r1))u'\in L(\Cut(r_1)).  
IH₂: Für alle u,vΣu'',v''\in\Sigma^* mit u1vL(r2)u''1v''\in L(r_2) gilt uL(Cut(r2))u''\in L(\Cut(r_2)).  

Beweis des Falls r=r1r2r=r_1r_2:  
Null():=\Null(\emptyset) := \emptyset  
Sei u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^*. Dann gibt es xL(r1)x\in L(r_1), yL(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=u1vx=u'1v', so dass u1vL(r1)u'1v' \in L(r_1) und u=uu=u' gilt. Nach IH₁ folgt u=uL(Cut(r1))u'=u\in L(\Cut(r_1)), also uL(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=u1vy=u''1v'' mit u1vL(r2)u''1v''\in L(r_2) und u=xuu=xu''. Nach IH₂ folgt uL(Cut(r2))u''\in L(\Cut(r_2)), also xuL(r1Cut(r2))L(Cut(r1r2))xu''\in L(r_1\Cut(r_2))\subseteq L(\Cut(r_1r_2)). Da u=xuu=xu'', gilt uL(Cut(r1r2))u\in L(\Cut(r_1r_2)).  

Insbesondere erfüllt x=uL(r1)x=u' \in L(r_1) (Fall 1) bzw. xuL(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):={vxwv,wΣx{0,ε}vwL}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(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r1Null(r2)\Null(r_1 r_2) := \Null(r_1) r_2 \mid r_1 \Null(r_2)
Null(r):=rNull(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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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 u11v1L(r1)u_1 1 v_1\in L(r_1) gilt u1L(Cut(r1))u_1\in L(\Cut(r_1)).
- Für alle u2,v2Σu_2,v_2\in\Sigma^* mit u21v2L(r2)u_2 1 v_2\in L(r_2) gilt u2L(Cut(r2))u_2\in L(\Cut(r_2)).

Beweis des Falls r=r1r2r=r_1r_2:
Sei u1vL(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, w1L(r1)w_1 \in L(r_1), w2L(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 u11v1L(r1)u_1 1 v_1 \in L(r_1). Nach Induktionshypothese für r1r_1 folgt u1L(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=u1L(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 u21v2L(r2)u_2 1 v_2 \in L(r_2). Nach Induktionshypothese für r2r_2 folgt u2L(Cut(r2))u_2 \in L(\Cut(r_2)) (IH2).
  Da w1L(r1)w_1 \in L(r_1) und u2L(Cut(r2))u_2 \in L(\Cut(r_2)), ist w1u2L(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=w1u2L(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 uL(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):={vxwv,wΣx{0,ε}vwL}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):=a0aa0\Null(a) := a \mid 0\,a \mid a\,0
Null(r1r2):=Null(r1)Null(r2)\Null(r_1 \mid r_2) := \Null(r_1) \mid \Null(r_2)
Null(r1r2):=Null(r1)r2r1Null(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(r1r2):=Cut(r1)Cut(r2)\Cut(r_1 \mid r_2) := \Cut(r_1) \mid \Cut(r_2)
Cut(r):=rCut(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 u1vL(r)u1v\in L(r) gilt, dass uL(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 u1vL(r1r2)u1v\in L(r_1r_2) mit u,vΣu,v\in\Sigma^* gilt uL(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 u1vL(r1)u'1v'\in L(r_1) gilt uL(Cut(r1))u'\in L(\Cut(r_1)).

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

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

Fall 1: kmk\geq m.  
Dann liegt das '1' in xx, also x=u1xx = u 1 x'' für ein xΣx''\in\Sigma^* (mit x=km|x''| = k-m). Somit ist u1xL(r1)u1x''\in L(r_1).  
Nach (IH1) gilt uL(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=y1yy = y' 1 y'' für y,yΣy',y''\in\Sigma^* mit y=mk1|y'|=m-k-1. Somit ist u=xyu = x y' und v=yv = y''.  
Nach (IH2) gilt yL(Cut(r2))y'\in L(\Cut(r_2)).  
Daher ist u=xyL(r1)L(Cut(r2))L(Cut(r1r2))u = x y'\in L(r_1)L(\Cut(r_2))\subseteq L(\Cut(r_1r_2)).