anthropic/claude-opus-4.1

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (4.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S → A | B
A → aAb | C
C → aC | ε
B → aB | D
D → bDa | ε

Grammatik für L2L_2:
S → aT
T → aTX | X
X → a | b | aX | bX

Grammatik für L3L_3:
S → XBY
X → aXb | ε
B → bB | b
Y → bYa | ε
0: wrong language: does not generate abaa

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
Regulärer Ausdruck: a(ab)+a(a|b)^+

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
Wort, falls LiLϵ(M)L_i\neq L_\epsilon(M), sonst „-“.
L1L_1: aaaa
L2L_2: aaaa
L3L_3: -

anthropic/claude-sonnet-4

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (4.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S -> A | B
A -> aAb | C
C -> aC | ε
B -> aB | D  
D -> bDa | ε

Grammatik für L2L_2:
S -> aAB
A -> aAC | ε
C -> a | b
B -> YB | Y
Y -> a | b

Grammatik für L3L_3:
S -> LMR
L -> aLb | ε
M -> bM | b
R -> bRa | ε
0: wrong language: does not generate abaa

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
a(a+b)+a(a+b)^+

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
L1L_1: ab
L2L_2: bb
L3L_3: -

deepseek/deepseek-chat-v3.1

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (4.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S -> A E | E B
A -> a A b | ε
B -> b B a | ε
E -> a E | ε

Grammatik für L2L_2:
S -> a S A | a A
A -> a | b | a A | b A

Grammatik für L3L_3:
S -> a S a | a S | S a | b S | b
2: wrong language: generates ab

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
Regulärer Ausdruck: aΣΣa\Sigma\Sigma^*
0: mismatch
0: could not parse value a\Sigma\Sigma^* for type re

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
L1L_1: aa
L2L_2: aaaa
L3L_3: -

deepseek/deepseek-r1-0528

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (6.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
SXCCDS \to X C \mid C D  
XaXbεX \to a X b \mid \varepsilon  
CaCεC \to a C \mid \varepsilon  
DbDaεD \to b D a \mid \varepsilon  

Grammatik für L2L_2:
SaSXaXTS \to a S X \mid a X T  
XabX \to a \mid b  
TaTbTεT \to a T \mid b T \mid \varepsilon  

Grammatik für L3L_3:
SXYS \to X Y  
XaXbXbεX \to a X b \mid X b \mid \varepsilon  
YbYabYbY \to b Y a \mid b Y \mid b

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
Regulärer Ausdruck: a(ab)(ab)a(a|b)(a|b)^*

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
L_1: b
L_2: ab
L_3: -

google/gemini-2.5-pro

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (6.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
SXCCYS \to XC \mid CY
XaXbεX \to aXb \mid \varepsilon
YbYaεY \to bYa \mid \varepsilon
CaCεC \to aC \mid \varepsilon

Grammatik für L2L_2:
SARS \to AR
AaAaaAbaaabA \to aAa \mid aAb \mid aa \mid ab
RaRbRεR \to aR \mid bR \mid \varepsilon

Grammatik für L3L_3:
SABCS \to ABC
AaAbεA \to aAb \mid \varepsilon
BbBbB \to bB \mid b
CbCaεC \to bCa \mid \varepsilon

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
Regulärer Ausdruck: a(ab)(ab)a(a|b)(a|b)^*

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
Wort, falls LiLϵ(M)L_i\neq L_\epsilon(M), sonst „-“.
L1L_1: b
L2L_2: b
L3L_3: -

openai/gpt-5

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (6.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S -> X A | A Y
X -> a X b | ε
Y -> b Y a | ε
A -> a A | ε

Grammatik für L2L_2:
S -> a S C | a C R
C -> a | b
R -> a R | b R | ε

Grammatik für L3L_3:
S -> T R
T -> a T E | ε
E -> b E | b
R -> b R | b R a | b

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
a(a|b)(a|b)*

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
Wort, falls LiLϵ(M)L_i\neq L_\epsilon(M), sonst „-“.
L1L_1: ε
L2L_2: b
L3L_3: -

openai/gpt-oss-120b

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (0.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_{1}  
SS ist der Startsymbol.  

SMNMaMbTTaTεNaNVVbVaε
\begin{aligned}
S &\to M \mid N\\
M &\to a\,M\,b \mid T\\
T &\to a\,T \mid \varepsilon\\
N &\to a\,N \mid V\\
V &\to b\,V\,a \mid \varepsilon
\end{aligned}


MM erzeugt aibiaka^{i}b^{i}a^{k} (Fall i=ji=j), NN erzeugt aibjaja^{i}b^{j}a^{j} (Fall j=kj=k).  

---

Grammatik für L2L_{2}  
SS ist der Startsymbol.

SaSXaXYXabYaYbYε
\begin{aligned}
S &\to a\,S\,X \mid a\,X\,Y\\
X &\to a \mid b\\
Y &\to a\,Y \mid b\,Y \mid \varepsilon
\end{aligned}


Jede Ableitung liefert ana^{n} gefolgt von exakt nn Symbolen aus {a,b}\{a,b\} (durch die XX’s) und danach beliebig viele weitere Symbole (durch YY). Damit gilt wn|w|\ge n und n>0n>0.

---

Grammatik für L3L_{3}  
SS ist der Startsymbol.

SABAaAbεBbBabBb
\begin{aligned}
S &\to A\,B\\
A &\to a\,A\,b \mid \varepsilon\\
B &\to b\,B\,a \mid b\,B \mid b
\end{aligned}


AA erzeugt aibia^{i}b^{i}.  
BB erzeugt ein Wort der Form bmakb^{m}a^{k} mit mk+1m\ge k+1.  
Damit hat jedes Wort die Form aibi+maka^{i}b^{i+m}a^{k} und erfüllt
j=i+m>i+kj=i+m > i+k. Alle Bedingungen von L3L_{3} sind erfüllt.
answer does not follow the template

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
Regulärer Ausdruck: a(a|b)+
0: mismatch
0: could not parse value a(a|b)+ for type re

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
L1L_1: a  
L2L_2: b  
L3L_3: -

qwen/qwen3-235b-a22b

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (6.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S → A B | C D  
A → a A b | ε  
B → a B | ε  
C → a C | ε  
D → b D a | ε  

Grammatik für L2L_2:
S → a X  
X → a X Y | Y  
Y → a Y | b Y | a | b  

Grammatik für L3L_3:
S → A B C  
A → a A b | ε  
B → b B | b  
C → b C a | ε

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
Regulärer Ausdruck: a(ab)+a(a|b)^+

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
Wort, falls LiLϵ(M)L_i\neq L_\epsilon(M), sonst „-“.
L1L_1: abab
L2L_2: abab
L3L_3: -

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

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (0.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S -> X | Y
X -> a X b A | A
A -> a A | \varepsilon
Y -> A E
E -> b E a | \varepsilon

Grammatik für L2L_2:
S -> a T
T -> a T D | D
D -> a | b

Grammatik für L3L_3:
S -> A B
A -> a A b | \varepsilon
B -> b B a | b
0: wrong language: generates aabaa
1: wrong language: does not generate abb
2: wrong language: does not generate bb

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
wrong answer for choice (0)
Regulärer Ausdruck: a(ab)+a(a|b)^+

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
L1L_1: bb
L2L_2: bb
L3L_3: -

x-ai/grok-4

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (6.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S \to P W | W Q
P \to a P b | \varepsilon
Q \to b Q a | \varepsilon
W \to a W | \varepsilon

Grammatik für L2L_2:
S \to a M G
M \to a M G | T
T \to G T | \varepsilon
G \to a | b

Grammatik für L3L_3:
S \to P E Q
P \to a P b | \varepsilon
Q \to b Q a | \varepsilon
E \to b E | b

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
Regulärer Ausdruck: a(ab)+a(a\cup b)^+

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
L1L_1: abab
L2L_2: abab
L3L_3: -

z-ai/glm-4.5

Exercise 5: Kontextfreie Sprachen

Gegeben sind folgende drei Sprachen über dem Alphabet Σ:={a,b}\Sigma := \{a,b\}:
L1:={aibjak:(i=jj=k)i,j,k0}L_1 := \{a^ib^ja^k : (i = j\vee j = k)\wedge i,j,k\geq 0\}
L2:={anw:wΣwnn>0}L_2 := \{a^nw : w\in \Sigma^* \wedge |w|\geq n\wedge n>0\}
L3:={aibjak:j>i+ki,j,k0}L_3 := \{a^ib^ja^k : j>i + k\wedge i,j,k\geq 0\}

Subproblem a (2.0/6.0P)

Geben Sie kontextfreie Grammatiken für L1,L2,L3L_1,L_2,L_3 mit jeweils höchstens 5 Nichtterminalen und 10 Produktionen an.

Hinweis: Sie dürfen ε\varepsilon-Produktionen verwenden.
Grammatik für L1L_1:
S → TA | AT
T → aTb | bTa | ε
A → aA | ε

Grammatik für L2L_2:
S → aSB | aT
B → aB | bB | a | b
T → aT | bT | a | b

Grammatik für L3L_3:
S → aSb | T
T → bT | bU
U → bU | bV
V → bVa | b
0: wrong language: generates baa
2: wrong language: does not generate b

Subproblem b (4.0/4.0P)

Genau eine der drei Sprachen ist sogar regulär. Entscheiden Sie welche und geben Sie einen regulären Ausdruck an, der die gleiche Sprache beschreibt.
L1L_1L2L_2L3L_3
a(a+b)^+

Subproblem c (3.0/3.0P)

Untenstehend finden Sie einen PDA MM, der mit leerem Keller akzeptiert und das initiale Kellerzeichen ZZ verwendet. Bestimmen Sie für jede Sprache Li{L1,L2,L3}L_i\in\{L_1,L_2,L_3\} jeweils, ob Lϵ(M)=LiL_\epsilon(M)=L_i gilt. Falls nein, geben Sie ein Wort ww mit Länge höchstens 2 an, sodass ww in genau einer der Sprachen Lϵ(M)L_\epsilon(M) und LiL_i ist.

Hinweis: Es gilt Lϵ(M)=LiL_\epsilon(M)=L_i für genau ein i{1,2,3}i\in\{1,2,3\}.
Die Transition „q,a,Xp,YZq, a, X \rightarrow p, YZ“ eines PDAs bedeutet, das der PDA in Zustand qq ist, Zeichen aa liest, und das oberste Stacksymbol XX hat. Anschließend geht der PDA in Zustand pp, nimmt XX vom Stack, und legt YZYZ auf den Stack (YY ist oben). Eine Transition mit a=εa=\varepsilon ist erlaubt, in dem Fall wird kein Zeichen eingelesen.
PDA M:
Zustände: q0, q1, q2, q3
Startzustand: q0
Initialzeichen: Z
Transitionen:
    q0, a, A -> q0, AA
    q0, a, Z -> q0, AZ
    q0, ε, A -> q1, A
    q0, ε, Z -> q1, Z
    q1, b, A -> q1, ε
    q1, b, Z -> q2, B
    q2, b, B -> q2, BB
    q2, ε, B -> q3, ε
    q3, a, B -> q3, ε
    q3, ε, B -> q3, ε
L1=Lϵ(M)L_1=L_\epsilon(M)L1Lϵ(M)L_1\neq L_\epsilon(M)L2=Lϵ(M)L_2=L_\epsilon(M)L2Lϵ(M)L_2\neq L_\epsilon(M)L3=Lϵ(M)L_3=L_\epsilon(M)L3Lϵ(M)L_3\neq L_\epsilon(M)
L1L_1: ab
L2L_2: aa
L3L_3: -