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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (2.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=ab(aba)X=ab(a^*b^*a)^*
Y=((ba)abb)Y=((b|a)a^* | bb)^*
Z=Z=\emptyset
0: wrong language: contains aba

Subproblem g (3.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Beweis: Angenommen, es existiert ein reversibler NFA N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F) mit L(N)=(aa)(bb)L(N) = (aa)^*(bb)^*.

Da aaL(N)aa \in L(N), existiert ein akzeptierender Pfad q0ap1ap2q_0 \xrightarrow{a} p_1 \xrightarrow{a} p_2 mit p2Fp_2 \in F.

Da bbL(N)bb \in L(N), existiert ein akzeptierender Pfad q0br1br2q_0 \xrightarrow{b} r_1 \xrightarrow{b} r_2 mit r2Fr_2 \in F.

Aus der Reversibilität folgt:
- Da p1δ(q0,a)p_1 \in \delta(q_0, a), gilt q0δ(p1,a)q_0 \in \delta(p_1, a)
- Da r1δ(q0,b)r_1 \in \delta(q_0, b), gilt q0δ(r1,b)q_0 \in \delta(r_1, b)  
- Da r2δ(r1,b)r_2 \in \delta(r_1, b), gilt r1δ(r2,b)r_1 \in \delta(r_2, b)

Somit gilt δ(r1,b){q0,r2}\delta(r_1, b) \supseteq \{q_0, r_2\}.

Betrachte den Pfad: q0br1bq0ap1ap2q_0 \xrightarrow{b} r_1 \xrightarrow{b} q_0 \xrightarrow{a} p_1 \xrightarrow{a} p_2

Dieser Pfad entspricht dem Wort bbaabbaa und endet im akzeptierenden Zustand p2p_2. Also gilt bbaaL(N)bbaa \in L(N).

Aber bbaa(aa)(bb)bbaa \notin (aa)^*(bb)^*, da in (aa)(bb)(aa)^*(bb)^* alle aa's vor allen bb's kommen müssen. Widerspruch!

Daher existiert kein reversibler NFA für (aa)(bb)(aa)^*(bb)^*.

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (0.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}
wrong answer for choice (2)

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(aba)abX=(a^*b^*a)^*ab
Y=((ba)abb)Y=((b\mid a)a^* \mid bb)^*
Z=Z=\emptyset

Subproblem g (0.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
wrong answer for choice (0)
Yes, there exists a reversible NFA for L((aa)(bb))L((aa)^*(bb)^*).

NFA: N=({q0,q1,q2},{a,b},δ,q0,{q0})N = (\{q_0, q_1, q_2\}, \{a,b\}, \delta, q_0, \{q_0\})

Transition function δ\delta:
- δ(q0,a)={q1}\delta(q_0, a) = \{q_1\}
- δ(q0,b)={q2}\delta(q_0, b) = \{q_2\}  
- δ(q1,a)={q0}\delta(q_1, a) = \{q_0\}
- δ(q1,b)=\delta(q_1, b) = \emptyset
- δ(q2,a)=\delta(q_2, a) = \emptyset
- δ(q2,b)={q0}\delta(q_2, b) = \{q_0\}

This NFA is reversible because for every transition qjδ(qi,x)q_j \in \delta(q_i, x), we have qiδ(qj,x)q_i \in \delta(q_j, x), and it recognizes exactly the strings in (aa)(bb)(aa)^*(bb)^*.

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(aba)abX=(a^*b^*a)^*ab
Y=(ab)Y=(a|b)^*
Z=Z=\emptyset

Subproblem g (0.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Beweis, dass kein reversibler NFA für L((aa)(bb))L((aa)^*(bb)^*) existiert:

Angenommen, es gibt einen reversiblen NFA NN mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*). Da NN reversibel ist, muss für jede Transition von Zustand pp zu Zustand qq auf Symbol xx eine Transition von qq zu pp auf xx existieren.

Betrachte die Zeichenkette bbLbb \in L. Nach Lesen von bbbb ist NN in einem Akzeptanzzustand qaccq_{acc}. Aufgrund der Reversibilität muss von qaccq_{acc} auf bb eine Transition zu einem Zustand qbq_b existieren, von dem aus auf bb eine Transition zu qaccq_{acc} führt. Da bbbb akzeptiert wird, muss von qbq_b auf bb nach qaccq_{acc} gehen.

Nun betrachte die Zeichenkette bLb \notin L. Nach Lesen von bb ist NN in einem Zustand qbq_b (nicht akzeptierend). Von qbq_b auf aa muss es eine Transition zu einem Zustand rr geben, da baLba \notin L und thus nicht akzeptiert werden darf. Aufgrund der Reversibilität muss von rr auf aa eine Transition zurück zu qbq_b existieren.

Jetzt kann NN die Zeichenkette baba lesen: von Start nach qbq_b auf bb, dann nach rr auf aa. Von rr aus kann auf aa nach qbq_b gegangen werden, und von qbq_b auf bb nach qaccq_{acc}. Thus wird die Zeichenkette baabbaab akzeptiert. However, baabbaab enthält aa nach bb und ist nicht in L((aa)(bb))L((aa)^*(bb)^*), da alle aa vor den bb stehen müssen. Dies ist ein Widerspruch zur Annahme that L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*).

Daher existiert kein reversibler NFA für L((aa)(bb))L((aa)^*(bb)^*).

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(aba)abX=(a^*b^*a)^*ab
Y=(ab)Y=(a \mid b)^*
Z=Z=\emptyset

Subproblem g (0.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Beweis durch Widerspruch: Angenommen, es gibt einen reversiblen NFA N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F) mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*).

Betrachte das Wort aaLaa \in L. Es gibt einen akzeptierenden Lauf, etwa q0arapq_0 \xrightarrow{a} r \xrightarrow{a} p mit pFp \in F.  
- Wegen Reversibilität gilt: Aus pδ(r,a)p \in \delta(r, a) folgt rδ(p,a)r \in \delta(p, a).  
- Für das Wort abLab \notin L gibt es einen Lauf, der im gleichen Zustand rr nach dem ersten aa endet (nicht notwendig derselbe Lauf, aber ein Zustand rr mit q0arq_0 \xrightarrow{a} r für aaaa). Somit existiert ein Zustand ss mit δ(r,b)=s\delta(r, b) = s.  
- Reversibilität impliziert: Aus sδ(r,b)s \in \delta(r, b) folgt rδ(s,b)r \in \delta(s, b).

Nun konstruieren wir einen Lauf für abbaLabba \notin L:  
- q0arq_0 \xrightarrow{a} r (nach erstem aa)  
- rbsr \xrightarrow{b} s (nach abab)  
- sbrs \xrightarrow{b} r (da δ(s,b)=r\delta(s, b) = r)  
- rapr \xrightarrow{a} p (da δ(r,a)p\delta(r, a) \ni p)  
Endzustand pFp \in F ist akzeptierend.

Dies wäre eine akzeptierende Berechnung für abbaabba, aber abbaLabba \notin L (da bb vor dem letzten aa), Widerspruch.  
Also existiert kein solcher reversibler NFA.

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(aba)abX=(a^*b^*a)^*ab
Y=((ab)abb)Y=((a|b)a^*|bb)^*
Z=Z=\emptyset

Subproblem g (3.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Nein, es gibt keinen solchen reversiblen NFA.

Beweis durch Widerspruch:

Angenommen, es existiert ein reversibler NFA N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F), der die Sprache L=L((aa)(bb))L = L((aa)^*(bb)^*) akzeptiert.

1.  Da das leere Wort ε\varepsilon in LL ist, muss der Startzustand q0q_0 ein Endzustand sein, d.h. q0Fq_0 \in F.

2.  Das Wort aaaa ist in LL. Also muss es einen Pfad q0aq1aq2q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_2 für Zustände q1,q2Qq_1, q_2 \in Q geben, sodass q2q_2 ein Endzustand ist (q2Fq_2 \in F).

3.  Das Wort aabbaabb ist in LL. Da der Pfad für aaaa in q2q_2 endet, muss es von q2q_2 aus einen akzeptierenden Pfad für bbbb geben. Sei dieser Pfad q2bq3bq4q_2 \xrightarrow{b} q_3 \xrightarrow{b} q_4 für Zustände q3,q4Qq_3, q_4 \in Q, sodass q4q_4 ein Endzustand ist (q4Fq_4 \in F).

4.  Da der NFA NN per Annahme reversibel ist, impliziert die Existenz eines Pfades von einem Zustand pp zu einem Zustand qq mit einem Wort ww die Existenz eines Pfades von qq nach pp mit dem gespiegelten Wort wRw^R. In unserem Fall sind die Wörter aaaa und bbbb Palindrome (aaR=aaaa^R=aa, bbR=bbbb^R=bb), daher gilt:
    *   Aus dem Pfad q0aaq2q_0 \xrightarrow{aa} q_2 folgt die Existenz eines Pfades q2aaq0q_2 \xrightarrow{aa} q_0.
    *   Aus dem Pfad q2bbq4q_2 \xrightarrow{bb} q_4 folgt die Existenz eines Pfades q4bbq2q_4 \xrightarrow{bb} q_2.

5.  Betrachten wir nun die Sprache Lq4L_{q_4}, die von NN akzeptiert wird, wenn wir in Zustand q4q_4 starten. Ein Wort ww ist in Lq4L_{q_4} genau dann, wenn es einen Pfad von q4q_4 zu einem Endzustand gibt, der mit ww beschriftet ist.

6.  Wenn ein Wort ww in Lq4L_{q_4} ist, dann ist das Wort aabbwaabbw in L(N)L(N), da es einen Pfad q0aabbq4q_0 \xrightarrow{aabb} q_4 gibt, der mit dem akzeptierenden Pfad für ww von q4q_4 aus verkettet werden kann.

7.  Gemäß der Definition von L=(aa)(bb)L = (aa)^*(bb)^* muss ein Wort, das mit aabbaabb beginnt und in LL ist, die Form aabb(bb)kaabb(bb)^k für ein k0k \ge 0 haben. Das bedeutet, wenn aabbwLaabbw \in L, muss w(bb)w \in (bb)^* sein. Folglich muss für die von q4q_4 aus akzeptierte Sprache gelten: Lq4(bb)L_{q_4} \subseteq (bb)^*.

8.  Aus den in Schritt 4 hergeleiteten Pfaden können wir einen neuen Pfad von q4q_4 aus konstruieren, indem wir sie aneinanderhängen:
    q4bbq2aaq0q_4 \xrightarrow{bb} q_2 \xrightarrow{aa} q_0.
    Dieser Pfad ist mit dem Wort bbaabbaa beschriftet.

9.  Da q0q_0 ein Endzustand ist (Schritt 1), ist dieser Pfad ein akzeptierender Pfad. Das bedeutet, das Wort bbaabbaa wird von NN akzeptiert, wenn man im Zustand q4q_4 startet. Also ist bbaaLq4bbaa \in L_{q_4}.

10. Wir haben nun einen Widerspruch:
    *   Aus Schritt 7 wissen wir: Lq4(bb)L_{q_4} \subseteq (bb)^*.
    *   Aus Schritt 9 wissen wir: bbaaLq4bbaa \in L_{q_4}.
    Jedoch ist das Wort bbaabbaa offensichtlich nicht in der Sprache (bb)(bb)^*.

Dieser Widerspruch zeigt, dass unsere anfängliche Annahme falsch sein muss. Es gibt also keinen reversiblen NFA für die Sprache L((aa)(bb))L((aa)^*(bb)^*).

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(aba)abX=(a^*b^*a)^*ab
Y=((ba)abb)Y=((b\mid a)a^*\mid bb)^*
Z=Z=\emptyset

Subproblem g (3.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Angenommen, es gäbe einen reversiblen NFA N mit L(N) = (aa)^*(bb)^*.
Dann liegen aa ∈ L(N) und bb ∈ L(N).

- Für bb gibt es also eine akzeptierende Lauf q0 —b→ q1 —b→ q2.
  Wegen Reversibilität gilt aus q1 —b→ q2 auch q2 —b→ q1 und insbesondere aus q0 —b→ q1 auch q1 —b→ q0. Also existiert ein Lauf auf bb, der nach q0 zurückkehrt: q0 —b→ q1 —b→ q0.

- Für aa gibt es eine akzeptierende Lauf von q0 nach einem Endzustand.

Verkettet man diese beiden Läufe, erhält man einen akzeptierenden Lauf auf bbaa:
q0 —b→ q1 —b→ q0 —a→ … —a→ f (f akzeptierend).
Also bbaa ∈ L(N).

Aber bbaa ∉ (aa)^*(bb)^* (denn nach einem b folgen wieder a’s), Widerspruch.
Folglich existiert kein reversibler NFA für diese Sprache.

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (2.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(aba)abX=(a^*b^*a)^*ab  
Y=((ab)a    bb)Y=((a|b)a^* \;|\; bb)^*  
Z=Z=\emptyset
1: mismatch
1: could not parse value ((a|b)a^* \;|\; bb)^* for type re

Subproblem g (0.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
wrong answer for choice (0)
Reversibler NFA NN für L=(aa)(bb)L = (aa)^*(bb)^*  

- Zustandsmenge: Q={q0,q1,q2}Q = \{q_0, q_1, q_2\}  
- Startzustand: q0q_0  
- Endzustände: F={q0}F = \{q_0\}  

- Übergangsfunktion δ\delta:  

δ(q0,a)={q1},δ(q1,a)={q0},δ(q0,b)={q2},δ(q2,b)={q0},δ(q1,b)=,δ(q2,a)=.
\begin{aligned}
\delta(q_0, a) &= \{q_1\}, & \delta(q_1, a) &= \{q_0\}, \\
\delta(q_0, b) &= \{q_2\}, & \delta(q_2, b) &= \{q_0\}, \\
\delta(q_1, b) &= \emptyset, & \delta(q_2, a) &= \emptyset.
\end{aligned}


Alle übrigen Übergänge sind leer (\emptyset).  

Warum ist der NFA reversibel?  
Für jedes Symbol x{a,b}x \in \{a,b\} gilt:
- Wenn q2δ(q1,x)q_2 \in \delta(q_1,x) (z.B. q1aq0q_1 \xrightarrow{a} q_0), dann ist zugleich q1δ(q2,x)q_1 \in \delta(q_2,x) (z.B. q0aq1q_0 \xrightarrow{a} q_1).  
- Analog für die bb-Übergänge zwischen q0q_0 und q2q_2.  

Damit erfüllt NN die Definition eines reversiblen NFA.

Sprachakzeptanz:  
- Durch abwechselnde aa-Übergänge zwischen q0q_0 und q1q_1 wird nur eine gerade Anzahl von aa’s akzeptiert (Endzustand muss q0q_0 sein).  
- Nachdem ein bb gelesen wurde, wechselt man zu q2q_2; weitere bb’s pendeln zwischen q2q_2 und q0q_0, also ebenfalls nur gerade Anzahl von bb’s führen zum Endzustand q0q_0.  
- Sobald man sich in q2q_2 befindet, gibt es keinen aa-Übergang, sodass nach Beginn des bb-Blocks kein weiteres aa mehr gelesen werden kann.  

Somit akzeptiert NN exakt die Sprache (aa)(bb)(aa)^*(bb)^*.

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(a^*b^*a)^*ab  
Y=((a|b)a^*|bb)^*  
Z=\emptyset

Subproblem g (3.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Angenommen, ein reversibler NFA NN existiert für L((aa)(bb))L((aa)^*(bb)^*). Dann muss für alle Übergänge in NN die Reversibilität gelten: Ist ein Zustand q2q_2 von q1q_1 mit xΣx\in\Sigma erreichbar, so auch umgekehrt.

Widerspruchsbeweis:  
Betrachte das Wort aabbaaL((aa)(bb))aabbaa \notin L((aa)^*(bb)^*), da nach bbs weitere aas vorkommen. NN muss dieses Wort ablehnen.  
- Der Teil aabba a b b wird von NN akzeptiert (da aabbLaabb \in L). Dazu muss es einen Pfad von q0q_0 nach qfq_f geben.  
- Da NN reversibel ist, können die bbs im Zustand q2q_2 durch bb-Übergänge wieder rückwärts traversiert werden.  
- Beim Verarbeiten der zweiten a-Sequenz aaaa können Übergänge in q0q_0 und weitere aa-Verarbeitung erfolgen, da NN nicht die Reihenfolge aas vor bbs erzwingen kann.  

Daraus ergibt sich ein akzeptierender Pfad für aabbaaaabbaa, was einen Widerspruch darstellt.  
Schluss: Es gibt keinen reversiblen NFA für L((aa)(bb))L((aa)^*(bb)^*).

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(aba)abX=(a^*b^*a)^*ab
Y=(a+b)Y=(a+b)^*
Z=Z=\emptyset

Subproblem g (1.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Es gibt keinen reversiblen NFA für L((aa)(bb))L((aa)^*(bb)^*).  

Beweis: Angenommen, es existiert ein reversibler NFA NN mit L(N)=LL(N) = L. Betrachte die Zeichenfolge s=aabbLs = aabb \in L. Da NN reversibel ist, bilden die Übergänge für aa und bb jeweils ungerichtete Graphen. Für ss führen zwei aa-Übergänge von q0q_0 zu einem Zustand mit gerader aa-Anzahl (zurück zu einem Start-Zustand-ähnlichen Zustand), gefolgt von zwei bb-Übergängen. Aufgrund der Reversibilität gilt aber auch: Die Zeichenfolge t=bbaat = bbaa (eine Permutation von ss) würde dieselben Zustandswechsel auslösen, da bb-Übergänge die "Rückkehr" in den Zustand vor den bb-Eingaben ermöglichen. Somit akzeptiert NN ebenfalls tLt \notin L, was ein Widerspruch ist.  
Allgemein sind Sprachen, die auf symbolweiser Reihenfolge basieren (wie aa's vor bb's), nicht durch reversible NFAs erkennbar, da Reversibilität die Eingabezeichen vertauschen kann, ohne die Erkennung zu beeinträchtigen.

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.

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

Subproblem a (2.0/2.0P)

Welche der folgenden Sprachen sind Residualsprachen von L((bba)b)L((bba)^*b)?
{b}\{b\}L(ba(bba)bε)L(ba(bba)^*b | \varepsilon)\emptyset

Subproblem b (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* eine Sprache mit LL=ΣLL = \Sigma^*. Welche Aussagen sind wahr?
LL ist unendlichεL\varepsilon \in LLLL=ΣLLL = \Sigma^*

Subproblem c (2.0/2.0P)

Sei LΣL \subseteq \Sigma^* regulär. Welche der folgenden Sprachen sind regulär?
{uRvu,vL}\{u^R v \mid u, v \in L\}{uRuuL}\{u^R u \mid u \in L\}{uvu,vLu=v}\{uv \mid u, v \in L \land |u| = |v|\}

Subproblem d (2.0/2.0P)

Welche der folgenden kontextfreien Grammatiken sind mehrdeutig?
SSSaS \rightarrow SS \mid aSSaSbεS \rightarrow Sa \mid Sb \mid \varepsilonSTTTaTbTabS \rightarrow TT\quad T \rightarrow aT \mid bT \mid a \mid b

Subproblem e (2.0/2.0P)

Sei AΣA \subseteq \Sigma^* regulär und BΣB \subseteq \Sigma^* kontextfrei. Welche der folgenden Sprachen sind kontextfrei?
ABA \cup \overline{B}AB\overline{A} \cup BABAB

Subproblem f (3.0/3.0P)

Geben Sie reguläre Ausdrücke XX, YY, ZZ über Σ\Sigma an, sodass die folgenden Gleichungen erfüllt sind.
XabaXabX \equiv a^*b^*aX \mid ab
Y(ba)aYbbYϵY \equiv (b\mid a)a^*Y \mid bbY \mid \epsilon
Za(ab)ZZ \equiv a^*(a \mid b)Z
X=(a^*b^*a)^*ab
Y=((b|a)a^*|bb)^*
Z=\emptyset

Subproblem g (3.0/3.0P)

Ein NFA (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) heißt reversibel, falls für alle Zustände q1,q2Qq_1, q_2 \in Q und für alle Zeichen xΣx \in \Sigma gilt: Falls q2δ(q1,x)q_2 \in \delta(q_1,x), so q1δ(q2,x)q_1 \in \delta(q_2,x). Mit anderen Worten: Falls man von q1q_1 mit xx in q2q_2 übergehen kann, so kann man auch von q2q_2 mit xx in q1q_1 übergehen.

Gibt es einen reversiblen NFA NN über Σ\Sigma mit L(N)=L((aa)(bb))L(N) = L((aa)^*(bb)^*)? Falls ja, geben Sie einen solchen NFA an; falls nein, beweisen Sie es.
Wahr, reversibler NFAFalsch, Beweis
Angenommen, es existiert ein reversibler NFA N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F) mit L(N)=L((aa)(bb))L(N)=L((aa)^*(bb)^*).

Da εL\varepsilon \in L, gilt q0Fq_0 \in F.

Da bbLbb \in L, existiert ein Zustand vδ(q0,b)v \in \delta(q_0,b) und ein Pfad von vv mit bb zu einem akzeptierenden Zustand. Insbesondere existiert wδ(v,b)w \in \delta(v,b) mit wFw \in F. Wegen Reversibilität gilt, da vδ(q0,b)v \in \delta(q_0,b), auch q0δ(v,b)q_0 \in \delta(v,b).

Da aaLaa \in L, existiert ein Pfad von q0q_0 mit aaaa zu einem akzeptierenden Zustand: Es gibt rδ(q0,a)r \in \delta(q_0,a) und sδ(r,a)s \in \delta(r,a) mit sFs \in F.

Betrachte das Wort bbaaLbbaa \notin L. Der folgende Pfad akzeptiert es: q0bvbq0arasFq_0 \xrightarrow{b} v \xrightarrow{b} q_0 \xrightarrow{a} r \xrightarrow{a} s \in F.

Dies ist ein Widerspruch, da bbaaLbbaa \notin L, aber NN es akzeptiert.

Daher existiert kein solcher reversibler NFA.