anthropic/claude-opus-4.1

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=((a∣b)(a∣b))∗r_1=((a|b)(a|b))^*
r2=(ab∣b)∗r_2=(ab|b)^*
r3=(ab∣b(ab)∗b)∗r_3=(ab|b(ab)^*b)^*

Subproblem g (3.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☒Wahr, DFA☐Falsch, Begründung 
M':
- Zustände: 0, 1, 2
- Startzustand: 2 (statt 0)
- Finalzustände: 2
- Transitionen: (gleich wie M)
  - 0, a → 1
  - 0, b → 2
  - 1, a → 0
  - 1, b → 2
  - 2, a → 0
  - 2, b → 2

Dann gilt L(M') = {ε} ∪ Σb ≠ Σb = L(M), aber beide haben dieselben Residualsprachen {Σb, {ε} ∪ Σb}.

anthropic/claude-sonnet-4

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=((a∣b)(a∣b))∗r_1=((a|b)(a|b))^*
r2=(b∣ab)∗r_2=(b|ab)^*
r3=(ab∣b(ab)∗b)∗r_3=(ab|b(ab)^*b)^*

Subproblem g (0.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☐Wahr, DFA☒Falsch, Begründung 
wrong answer for choice (0)
No such DFA M' exists. If two DFAs have the same set of residual languages, then by the Myhill-Nerode theorem they have identical equivalence classes. Since a language is completely determined by which equivalence classes have ε in their residual language, and the residual languages are the same, the languages must be equal: L(M) = L(M').

deepseek/deepseek-chat-v3.1

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=((a+b)(a+b))∗r_1=((a+b)(a+b))^*
r2=(b+ab)∗r_2=(b+ab)^*
r3=((ab)∗b(ab)∗b)∗(ab)∗r_3=((ab)^*b(ab)^*b)^*(ab)^*

Subproblem g (0.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☐Wahr, DFA☒Falsch, Begründung 
wrong answer for choice (0)
Die Sprache L(M)L(M) besteht aus allen Wörtern, die mit bb enden. Für jedes Wort ww ist die Residualsprache L(M)w={x∣wx∈L(M)}={x∣x endet mit b}=L(M)L(M)^w = \{x \mid w x \in L(M)\} = \{x \mid x \text{ endet mit } b\} = L(M). Daher ist die Menge aller Residualsprachen von L(M)L(M) gleich {L(M)}\{L(M)\}. Wenn eine andere Sprache L′L' die gleiche Menge von Residualsprachen hat, dann gilt insbesondere L′=L′ε=L(M)L' = L'^\varepsilon = L(M). Somit gibt es keine Sprache L′≠L(M)L' \neq L(M) mit den gleichen Residualsprachen, und daher auch keinen entsprechenden DFA M′M'.

deepseek/deepseek-r1-0528

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=((a∣b)(a∣b))∗r_1=((a|b)(a|b))*
r2=(b∣ab)∗r_2=(b|ab)*
r3=((ab)∗b(ab)∗b)∗(ab)∗r_3=((ab)*b(ab)*b)*(ab)*

Subproblem g (3.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☒Wahr, DFA☐Falsch, Begründung 
Ja, es gibt einen solchen DFA M′M'.  
M′M' wird definiert durch:  
- Zustände: qε,qa,qbq_\varepsilon, q_a, q_b  
- Startzustand: qεq_\varepsilon  
- Finalzustände: qε,qbq_\varepsilon, q_b  
- Transitionen:  
  - δ(qε,a)=qa\delta(q_\varepsilon, a) = q_a  
  - δ(qε,b)=qb\delta(q_\varepsilon, b) = q_b  
  - δ(qa,a)=qa\delta(q_a, a) = q_a  
  - δ(qa,b)=qb\delta(q_a, b) = q_b  
  - δ(qb,a)=qa\delta(q_b, a) = q_a  
  - δ(qb,b)=qb\delta(q_b, b) = q_b  

Erklärung:  
- L(M)={w∈{a,b}∗∣w endet mit b}L(M) = \{w \in \{a,b\}^* \mid w \text{ endet mit } b\} (ohne ε\varepsilon).  
- L(M′)={ε}∪{w∈{a,b}∗∣w endet mit b}L(M') = \{\varepsilon\} \cup \{w \in \{a,b\}^* \mid w \text{ endet mit } b\}.  
- Die Residualsprachen beider Sprachen sind identisch: {{x∣x endet mit b},{ε}∪{x∣x endet mit b}}\{ \{x \mid x \text{ endet mit } b\}, \{\varepsilon\} \cup \{x \mid x \text{ endet mit } b\} \}.  
- Aber L(M)≠L(M′)L(M) \neq L(M'), da ε∈L(M′)\varepsilon \in L(M') aber ε∉L(M)\varepsilon \notin L(M).

google/gemini-2.5-pro

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=((a∣b)(a∣b))∗r_1=((a|b)(a|b))^*
r2=(b∣ab)∗r_2=(b|ab)^*
r3=(ab∣b(ab)∗b)∗r_3=(ab|b(ab)^*b)^*

Subproblem g (3.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☒Wahr, DFA☐Falsch, Begründung 
Der gesuchte DFA M′M' hat die folgende Spezifikation:
Zustände: 0, 1, 2
Startzustand: 2
Finalzustände: {2}
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2

openai/gpt-5

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=((a∣b)(a∣b))∗r_1=((a|b)(a|b))*
r2=(b∣ab)∗r_2=(b|ab)*
r3=(ab)∗(b(ab)∗b(ab)∗)∗r_3=(ab)*(b(ab)*b(ab)*)*

Subproblem g (3.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☒Wahr, DFA☐Falsch, Begründung 
Zustände: A, B
Startzustand: A
Finalzustände: A
Transitionen:
    A, a -> B
    A, b -> A
    B, a -> B
    B, b -> A

openai/gpt-oss-120b

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

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

Subproblem g (3.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☒Wahr, DFA☐Falsch, Begründung 
DFA M′

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

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


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

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


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

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

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


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

qwen/qwen3-235b-a22b

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=((a∣b)(a∣b))∗r_1=((a|b)(a|b))^*  
r2=(b∣ab)∗r_2=(b|ab)^*  
r3=(ab+b(ab)∗b)∗r_3=(ab + b(ab)^*b)^*

Subproblem g (0.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☐Wahr, DFA☒Falsch, Begründung 
wrong answer for choice (0)
Falsch. Die Residualsprachen einer Sprache sind eindeutig bestimmt und entsprechen den Zuständen des minimalen DFAs. Da der gegebene DFA M nicht minimal ist (Zustände 0 und 1 sind äquivalent), hat jede Sprache mit denselben Residualsprachen denselben minimalen DFA wie M und damit dieselbe Sprache. Daher kann es keinen solchen DFA M' geben.

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

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=((a+b)(a+b))∗r_1=((a+b)(a+b))^*
r2=(b+ab)∗r_2=(b+ab)^*
r3=(ab+b(ab)∗b)∗r_3=(ab + b(ab)^*b)^*

Subproblem g (0.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☐Wahr, DFA☒Falsch, Begründung 
wrong answer for choice (0)
Nein. Die Sprache L(M)=Σ∗bL(M) = \Sigma^*b hat ausschließlich die Residualsprache L(M)w=Σ∗bL(M)^w = \Sigma^*b für alle w∈Σ∗w \in \Sigma^*. 
Somit ist die Menge der Residualsprachen {Σ∗b}\{ \Sigma^*b \}. 
Falls L(M′)L(M') dieselbe Menge von Residualsprachen hätte, müsste L(M′)=L(M′)ε=Σ∗b=L(M)L(M') = L(M')^\varepsilon = \Sigma^*b = L(M) gelten. 
Daher kann kein solcher DFA M′M' mit L(M′)≠L(M)L(M') \neq L(M) existieren.

x-ai/grok-4

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (2.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☒L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei

Subproblem f (3.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r_1=((a+b)(a+b))^*
r_2=(ab + b)^*
r_3=((ab)^* b (ab)^* b (ab)^*)^* (ab)^*

Subproblem g (3.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☒Wahr, DFA☐Falsch, Begründung 
Zustände: 0, 1, 2  
Startzustand: 2  
Finalzustände: 2  
Transitionen:  
    0, a -> 1  
    0, b -> 2  
    1, a -> 0  
    1, b -> 2  
    2, a -> 0  
    2, b -> 2

z-ai/glm-4.5

Exercise 1: Quiz: Reguläre und kontextfreie Sprachen

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
Jede Frage bringt 2P.

In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={a,b}\Sigma:=\{a,b\}.

Subproblem a (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* eine endliche Sprache mit ∣L∣=∣L∗∣|L|=|L^*|. Welche Aussagen sind wahr?
☒LL ist regulär☒ε∈L\varepsilon\in L☒∣L∣=∣LL∣|L|=|LL|

Subproblem b (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* und L′:={w∈L:∣w∣2≤10∣w∣}L':=\{w\in L : |w|^2\le 10|w|\}. Welche Aussagen sind wahr?
☒L′L' ist regulär☒L′L' ist kontextfrei☒L′L' ist deterministisch kontextfrei

Subproblem c (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* regulär und k>0k>0. Welche der folgenden Sprachen sind regulär?
☒{w∈L:∣w∣≡0(modk)}\{w\in L: |w| \equiv 0\pmod k\}☒{w1...wk:w1,...,wk∈L}\{w_1...w_k: w_1,...,w_k\in L\}☐{wk:w∈L}\{w^k: w\in L\}

Subproblem d (2.0/2.0P) 

Sei L⊆Σ∗L\subseteq\Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?

Hinweis: LR:={xk...x1:x1...xk∈L∧x1,...,xk∈Σ∧k≥0}L^R:=\{x_k...x_1 : x_1...x_k\in L\wedge x_1,...,x_k\in\Sigma\wedge k\ge0\} ist die Spiegelung von LL.
☐L‾\overline{L}☒L∪LRL\cup L^R☐L∩LRL\cap L^R

Subproblem e (0.0/2.0P) 

Sei GG die Grammatik mit Produktionen S→aTS\rightarrow aT, T→SbT\rightarrow Sb. Welche Aussagen sind wahr?
☐GG ist rechtslinear☒GG ist kontextfrei☐L(G)L(G) ist regulär☒L(G)L(G) ist kontextfrei 
wrong answer for choice (2)

Subproblem f (1.0/3.0P) 

Seien L1,L2,L3⊆{a,b}∗L_1,L_2,L_3\subseteq\{a,b\}^* Sprachen, sodass L1L_1 genau die Wörter gerader Länge enthält, L2L_2 genau die Wörter enthält, in denen auf jedes aa unmittelbar ein bb folgt, und L3:=L1∩L2L_3:= L_1\cap L_2. Es gilt etwa ε,ab,babb∈L3\varepsilon,ab,babb\in L_3 und b,ba,aabb∉L3b,ba,aabb\notin L_3. Geben Sie reguläre Ausdrücke r1,r2,r3r_1,r_2,r_3 an, sodass L(ri)=LiL(r_i)=L_i, für i∈{1,2,3}i\in\{1,2,3\}.

r1=(aa+ab+ba+bb)∗r_1=(aa+ab+ba+bb)^*
r2=b∗(ab)∗r_2=b^*(ab)^*
r3=(bb+ab)∗r_3=(bb+ab)^*
1: wrong language: does not contain abb
2: wrong language: does not contain babb

Subproblem g (0.0/3.0P) 

Sei MM der folgende DFA. Gibt es einen DFA M′M', sodass L(M)L(M) und L(M′)L(M') die gleichen Residualsprachen haben, aber nicht gleich sind; also {L(M)w:w∈Σ∗}={L(M′)w:w∈Σ∗}\{L(M)^w:w\in\Sigma^*\}=\{L(M')^w:w\in\Sigma^*\} und L(M)≠L(M′)L(M)\ne L(M')?

Falls ja, geben Sie einen solchen DFA an; falls nein, begründen Sie Ihre Antwort kurz.
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 2
Transitionen:
    0, a -> 1
    0, b -> 2
    1, a -> 0
    1, b -> 2
    2, a -> 0
    2, b -> 2
☐Wahr, DFA☒Falsch, Begründung 
wrong answer for choice (0)
According to the Myhill-Nerode theorem, the set of residual languages of a language L uniquely determines L. If two DFAs have the same set of residual languages, they must recognize the same language. Therefore, there cannot exist a DFA M' such that L(M) and L(M') have the same residual languages but L(M) ≠ L(M').