anthropic/claude-opus-4.1

Exercise 2: Residualsprachen und Minimierung


Subproblem a (3.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): bb
(0,4): bb
(0,5): ε\varepsilon
(1,2): aa
(1,3): bb
(1,4): bb
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon
4 wrong words (-2P)

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Aus der Äquivalenztabelle ergibt sich die Menge SS durch Identifikation der Zustände, die in keinem Paar mit einem anderen Zustand äquivalent sind. In der Tabelle sehen wir, dass nur die Paare (0,1) und (3,4) mit "==" markiert sind. Das bedeutet:
- Zustände 0 und 1 sind zueinander äquivalent, also [0]M=[1]M={0,1}[0]_M = [1]_M = \{0,1\}
- Zustände 3 und 4 sind zueinander äquivalent, also [3]M=[4]M={3,4}[3]_M = [4]_M = \{3,4\}
- Zustand 2 hat kein "==" in seiner Zeile/Spalte, ist also nur zu sich selbst äquivalent: [2]M={2}[2]_M = \{2\}
- Zustand 5 hat kein "==" in seiner Zeile/Spalte, ist also nur zu sich selbst äquivalent: [5]M={5}[5]_M = \{5\}

Daher enthält SS genau die Zustände 2 und 5.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^na^n\}
Lcban=∅L^{cba^n}=\emptyset
Lan={ucuRan:u∈{a,b}∗}L^{a^n}=\{ucu^Ra^n : u \in \{a,b\}^*\}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Sei i,j∈Ni,j \in \mathbb{N} mit i≠ji \neq j. Wir zeigen, dass Lai≠LajL^{a^i} \neq L^{a^j}.

Betrachte das Wort bib^i. Wir zeigen, dass bi∈Lajb^i \in L^{a^j} aber bi∉Laib^i \notin L^{a^i}.

Behauptung 1: bi∉Laib^i \notin L^{a^i}
Damit bi∈Laib^i \in L^{a^i} gilt, müsste aibi∈La^ib^i \in L gelten. Da L={anbm:n,m≥0∧n≠m}L = \{a^nb^m : n,m \geq 0 \land n \neq m\} und hier n=i=mn = i = m, gilt aibi∉La^ib^i \notin L. Also ist bi∉Laib^i \notin L^{a^i}.

Behauptung 2: bi∈Lajb^i \in L^{a^j} (für i≠ji \neq j)
Damit bi∈Lajb^i \in L^{a^j} gilt, muss ajbi∈La^jb^i \in L gelten. Da j≠ij \neq i, ist die Bedingung n≠mn \neq m in der Definition von LL erfüllt, und somit gilt ajbi∈La^jb^i \in L. Also ist bi∈Lajb^i \in L^{a^j}.

Da bib^i in LajL^{a^j} enthalten ist, aber nicht in LaiL^{a^i}, folgt Lai≠LajL^{a^i} \neq L^{a^j}.

Dies zeigt, dass alle Residualsprachen Lw0,Lw1,Lw2,...L^{w_0}, L^{w_1}, L^{w_2}, ... paarweise verschieden sind. Da es unendlich viele verschiedene Residualsprachen gibt, ist LL nach dem Satz von Myhill-Nerode nicht regulär.

anthropic/claude-sonnet-4

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Ein Zustand qq ist nur zu sich selbst äquivalent, wenn für alle anderen Zustände p≠qp \neq q das Paar (q,p)(q,p) in der Tabelle ein Trennwort (nicht "==") hat. Aus der Tabelle sehen wir, dass:
- Zustand 2: Alle Paare (0,2), (1,2), (2,3), (2,4), (2,5) haben Trennwörter
- Zustand 5: Alle Paare (0,5), (1,5), (2,5), (3,5), (4,5) haben Trennwörter
- Die anderen Zustände haben mindestens ein Paar mit "==": (0,1) und (3,4)

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^na^n\}
Lcban=∅L^{cba^n}=\emptyset
Lan={ycyRan:y∈{a,b}∗}L^{a^n}=\{ycy^Ra^n : y \in \{a,b\}^*\}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:

Zunächst bestimme ich die Residualsprachen LanL^{a^n}:

Lan={v:anv∈L}L^{a^n} = \{v : a^n v \in L\}

Da L={akbm:k,m≥0,k≠m}L = \{a^k b^m : k,m \geq 0, k \neq m\} und anva^n v von der Form akbma^k b^m sein muss, folgt dass vv von der Form ajbma^j b^m mit j≥0,m≥0j \geq 0, m \geq 0 sein muss, wobei n+j≠mn+j \neq m gelten muss.

Also: Lan={ajbm:j≥0,m≥0,n+j≠m}L^{a^n} = \{a^j b^m : j \geq 0, m \geq 0, n+j \neq m\}

Nun zeige ich die paarweise Verschiedenheit:

Fall 1: i=0,j≥1i = 0, j \geq 1
Betrachte das Wort bjb^j. 
- bj∈La0b^j \in L^{a^0}, da bj=a0bjb^j = a^0 b^j und 0≠j0 \neq j (für j≥1j \geq 1)
- bj∉Lajb^j \notin L^{a^j}, da für bj=akbmb^j = a^k b^m mit j+k≠mj+k \neq m folgt k=0,m=jk=0, m=j, also j+0≠jj+0 \neq j, was falsch ist

Daher La0≠LajL^{a^0} \neq L^{a^j} für alle j≥1j \geq 1.

Fall 2: i,j≥1,i≠ji,j \geq 1, i \neq j
Betrachte das Wort bib^i.
- bi∈Lajb^i \in L^{a^j}, da bi=a0bib^i = a^0 b^i und j+0=j≠ij+0 = j \neq i (da i≠ji \neq j)
- bi∉Laib^i \notin L^{a^i}, da für bi=akbmb^i = a^k b^m mit i+k≠mi+k \neq m folgt k=0,m=ik=0, m=i, also i+0≠ii+0 \neq i, was falsch ist

Daher Lai≠LajL^{a^i} \neq L^{a^j} für alle i≠j≥1i \neq j \geq 1.

Da alle Residualsprachen Lw0,Lw1,Lw2,…L^{w_0}, L^{w_1}, L^{w_2}, \ldots paarweise verschieden sind, hat LL unendlich viele verschiedene Residualsprachen und ist somit nicht regulär.

deepseek/deepseek-chat-v3.1

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Aus der Äquivalenztabelle ist ersichtlich, dass alle Paare, die den Zustand 2 enthalten, ein unterscheidendes Wort haben (z.B. (0,2): aa, (1,2): aa, (2,3): aa, (2,4): aa, (2,5): ε\varepsilon), sodass Zustand 2 von allen anderen Zuständen unterscheidbar ist und somit nur zu sich selbst äquivalent ist. Ebenso haben alle Paare mit Zustand 5 ein unterscheidendes Wort (z.B. (0,5): ε\varepsilon, (1,5): ε\varepsilon, (2,5): ε\varepsilon, (3,5): ε\varepsilon, (4,5): ε\varepsilon), sodass Zustand 5 nur zu sich selbst äquivalent ist. Die Zustände 0 und 1 sind äquivalent zueinander (markiert mit "=="), und die Zustände 3 und 4 sind äquivalent zueinander, daher sind ihre Äquivalenzklassen nicht singulär.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^na^n\}
Lcban=∅L^{cba^n}=\emptyset
Lan={ycyRan∣y∈{a,b}∗}L^{a^n}=\{y c y^R a^n \mid y \in \{a,b\}^*\}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i} \ne L^{w_j} für i,j∈N,i≠ji,j \in \mathbb{N}, i \ne j:
Sei i≠ji \ne j. Betrachte das Wort bib^i. Da i≠ji \ne j gilt, ist ajbi∈La^j b^i \in L, weil die Anzahl der a's jj und der b's ii ist und j≠ij \ne i. Thus, bi∈Lajb^i \in L^{a^j}. however, aibi∉La^i b^i \notin L, weil i=ii = i, also bi∉Laib^i \notin L^{a^i}. Daher ist Lai≠LajL^{a^i} \ne L^{a^j}.

deepseek/deepseek-r1-0528

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Ein Zustand qq gehört zu SS genau dann, wenn er nicht äquivalent zu irgendeinem anderen Zustand p≠qp \neq q ist. In der Äquivalenztabelle aus Teil a) zeigt ein Gleichheitszeichen „==" an, dass zwei Zustände äquivalent sind. Für SS müssen wir daher Zustände identifizieren, bei denen kein Paar (q,p)(q,p) mit p≠qp \neq q als äquivalent markiert ist:
- Zustand 2: Alle Paare (2,p)(2,p) für p≠2p \neq 2 sind mit trennenden Wörtern markiert ((2,0):a(2,0):a, (2,1):a(2,1):a, (2,3):a(2,3):a, (2,4):a(2,4):a, (2,5):ε(2,5):\varepsilon), also ist 22 nur zu sich selbst äquivalent.
- Zustand 5: Alle Paare (5,p)(5,p) für p≠5p \neq 5 sind mit trennenden Wörtern markiert (implizit aus der Tabelle, z.B. (5,0):ε(5,0):\varepsilon via (0,5)(0,5), (5,2):ε(5,2):\varepsilon via (2,5)(2,5), etc.), also ist 55 nur zu sich selbst äquivalent.
- Andere Zustände (0,1,3,4) sind jeweils äquivalent zu mindestens einem anderen Zustand (0=10=1, 3=43=4) und gehören daher nicht zu SS.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1},{2},{3,4},{5}\{0,1\}, \{2\}, \{3,4\}, \{5\}
Startzustand: {0,1}\{0,1\}
Finalzustände: {5}\{5\}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{ b^n a^n \}
Lcban=∅L^{cba^n}=\emptyset
Lan={vcvRan∣v∈{a,b}∗}L^{a^n}=\{ v c v^R a^n \mid v \in \{a,b\}^* \}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Seien i,j∈Ni, j \in \mathbb{N} mit i≠ji \neq j beliebig. Betrachte das Wort z=bjz = b^j.  
- z∈Lwiz \in L^{w_i}, denn wiz=aibj∈Lw_i z = a^i b^j \in L (da i≠ji \neq j).  
- z∉Lwjz \notin L^{w_j}, denn wjz=ajbj∉Lw_j z = a^j b^j \notin L (da j=jj = j).  
Somit gilt Lwi≠LwjL^{w_i} \neq L^{w_j}, da zz die Sprachen trennt.  
Da i,ji, j beliebig mit i≠ji \neq j gewählt wurden, sind die Residualsprachen Lw0,Lw1,…L^{w_0}, L^{w_1}, \dots paarweise verschieden.

google/gemini-2.5-pro

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2, 5\}

Erklärung:
Die Menge SS enthält alle Zustände qq, die zu keinem anderen Zustand pp äquivalent sind. In der Äquivalenztabelle erkennt man diese Zustände daran, dass in der Zeile und Spalte, die dem Zustand qq entsprechen, kein Gleichheitszeichen „==" vorkommt. Dies ist für die Zustände 2 und 5 der Fall.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
<empty>
no answer given

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^na^n\}
Lcban=∅L^{cba^n}=\emptyset
Lan={wcwRan∣w∈{a,b}∗}L^{a^n}=\{w c w^R a^n \mid w \in \{a,b\}^*\}

Subproblem f (3.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Seien i,j∈Ni, j \in \mathbb{N} mit i≠ji \ne j. Wir müssen zeigen, dass die Residualsprachen LwiL^{w_i} und LwjL^{w_j} verschieden sind.
Nach Definition ist wn=anw_n=a^n, also betrachten wir LaiL^{a^i} und LajL^{a^j}.

Die Residualsprache zu einem Wort uu ist definiert als Lu={v∈{a,b}∗∣uv∈L}L^u = \{v \in \{a,b\}^* \mid uv \in L\}.
Für u=aku=a^k besteht die Sprache LakL^{a^k} aus allen Wörtern vv, für die akv∈L={anbm∣n,m≥0∧n≠m}a^k v \in L = \{a^n b^m \mid n,m\ge0 \wedge n\ne m\} gilt.
Damit akva^k v die Form anbma^nb^m hat, muss vv von der Form bmb^m für ein m≥0m \ge 0 sein.
Die Bedingung n≠mn \ne m wird dann zu k≠mk \ne m.
Also ist die Residualsprache Lak={bm∣m≥0∧m≠k}L^{a^k} = \{b^m \mid m \ge 0 \land m \ne k\}.

Um zu beweisen, dass Lai≠LajL^{a^i} \ne L^{a^j} für i≠ji \ne j, suchen wir ein Wort zz, das in einer der Sprachen liegt, aber nicht in der anderen. Wir wählen z=biz = b^i.

- Wir prüfen, ob z∈Laiz \in L^{a^i}:
Das Wort z=biz=b^i liegt in Lai={bm∣m≥0∧m≠i}L^{a^i} = \{b^m \mid m \ge 0 \land m \ne i\} genau dann, wenn m=im=i die Bedingung m≠im \ne i erfüllt. Dies ist offensichtlich falsch. Also bi∉Laib^i \notin L^{a^i}.

- Wir prüfen, ob z∈Lajz \in L^{a^j}:
Das Wort z=biz=b^i liegt in Laj={bm∣m≥0∧m≠j}L^{a^j} = \{b^m \mid m \ge 0 \land m \ne j\} genau dann, wenn m=im=i die Bedingung m≠jm \ne j erfüllt. Da wir i≠ji \ne j angenommen haben, ist diese Bedingung wahr. Also bi∈Lajb^i \in L^{a^j}.

Da wir ein Wort z=biz=b^i gefunden haben, für das z∈Lajz \in L^{a^j} und z∉Laiz \notin L^{a^i} gilt, sind die beiden Residualsprachen verschieden. Da dies für jedes Paar i≠ji \ne j aus N\mathbb{N} gilt, gibt es unendlich viele paarweise verschiedene Residualsprachen.

openai/gpt-5

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Ein Zustand gehört genau dann zu SS, wenn er in der Äquivalenztabelle mit keinem anderen Zustand ein „=“ bildet. In der Tabelle aus (a) gibt es Gleichheit nur für (0,1) und (3,4). Für Zustand 2 steht bei allen Paaren mit anderen Zuständen ein Unterscheidungswort (z.B. „a“ bzw. bei (2,5) „ε“), und für Zustand 5 unterscheidet „ε“ ihn von allen nicht-finalen Zuständen. Daher sind nur 2 und 5 alleinstehend.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^na^n\}
Lcban=∅L^{cba^n}=\emptyset
Lan={ wcwRan∣w∈{a,b}∗}L^{a^n}=\{\,w c w^R a^n \mid w\in\{a,b\}^*\}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Sei i≠ji\neq j beliebig und setze x:=bix:=b^i. Dann gilt
- aix=aibi∉La^i x = a^i b^i \notin L, da die Anzahlen von aa und bb gleich sind. Also x∉Laix\notin L^{a^i}.
- ajx=ajbi∈La^j x = a^j b^i \in L, da ajbia^j b^i die Form anbma^n b^m hat und wegen j≠ij\neq i auch n≠mn\neq m. Also x∈Lajx\in L^{a^j}.

Damit ist Lai≠LajL^{a^i}\neq L^{a^j} für alle i≠ji\neq j. Es gibt also unendlich viele paarweise verschiedene Residualsprachen von LL. Nach dem Satz von Myhill–Nerode ist LL daher nicht regulär.

openai/gpt-oss-120b

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
$S=\{2,5\}$

Erklärung:<br>
Aus der Äquivalenztabelle sehen wir, dass nur die Paare **(0,1)** und **(3,4)** mit „$=$“ markiert sind, also jeweils äquivalente Zustände besitzen. Alle anderen Paare erhalten ein unterscheidendes Wort (z. B. „$a$“, „$ba$“ oder „$\varepsilon$“), was bedeutet, dass diese Zustände **nicht** äquivalent sind. Damit ergeben sich die folgenden Äquivalenzklassen:

- $\{0,1\}$ (wegen (0,1) =)<br>
- $\{3,4\}$ (wegen (3,4) =)<br>
- $\{2\}$ (kein anderes $q$ ist zu 2 gleich)<br>
- $\{5\}$ (kein anderes $q$ ist zu 5 gleich)

Die Zustände, deren Äquivalenzklasse nur aus sich selbst besteht, sind also $2$ und $5$, was exakt die Menge $S$ liefert.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: \{0,1\}, \{3,4\}, \{2\}, \{5\}  
Startzustand: \{0,1\}  
Finalzustände: \{5\}  
Transitionen:
{0,1}, a -> {3,4} 
{0,1}, b -> {2}
{3,4}, a -> {0,1} 
{3,4}, b -> {3,4}
{2}, a -> {5} 
{2}, b -> {3,4}
{5}, a -> {5} 
{5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon  
1: abab  
2: bb  
3: ε\varepsilon  
4: baabaa  
5: aaaa  
6: aa  
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={ b na n }L^{a^nb^nc}=\{\,b^{\,n}a^{\,n}\,\}  
Lcban=∅L^{cba^n}=\emptyset  
Lan={ v c vR a n∣v∈{a,b}∗ }L^{a^n}=\{\,v\,c\,v^{R}\,a^{\,n}\mid v\in\{a,b\}^{*}\,\}

Subproblem f (3.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=a nw_n := a^{\,n}  

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N, i≠ji,j\in\mathbb{N},\,i\ne j:

Für ein festes k∈Nk\in\mathbb{N} betrachten wir das Residuum nach dem Präfix aka^{k}:
Lak={ x∈{a,b}∗∣akx∈L }.
L^{a^{k}}=\{\,x\in\{a,b\}^* \mid a^{k}x\in L\,\}.


Da jedes Wort in LL genau aus einer Block von aa’s gefolgt von einem Block von bb’s besteht, ist jedes zulässiges Folgewort xx zwingend von der Form bmb^{m} (ein weiteres aa würde die Struktur von LL zerstören).  
Weiter gilt:

akbm∈L  ⟺  k≠m.
a^{k}b^{m}\in L 
\iff k\neq m .


Damit

Lak={ bm∣m∈N, m≠k }.(1)
L^{a^{k}} = \{\,b^{m}\mid m\in\mathbb{N},\ m\neq k\,\}.
\tag{1}


Nun sei i≠ji\neq j. Ohne Beschränkung der Allgemeinheit sei i<ji<j.  
Betrachte das Wort bib^{i}.

* Nach (1) ist bi∉Laib^{i}\notin L^{a^{i}}, weil dort genau das Wort bib^{i} fehlt (es erfüllt m=im=i).
* Ebenfalls nach (1) ist bi∈Lajb^{i}\in L^{a^{j}}, weil i≠ji\neq j und damit bib^{i} nicht das verbotene Wort bjb^{j} ist.

Somit enthält LajL^{a^{j}} das Wort bib^{i}, während LaiL^{a^{i}} dieses Wort nicht enthält. Also
Lai≠Laj.
L^{a^{i}}\neq L^{a^{j}}.


Da dies für jedes unterschiedliche Paar i,ji,j gilt, gibt es unendlich viele paarweise verschiedene Residualsprachen von LL. Nach dem Myhill‑Nerode‑Theorem ist LL deshalb nicht regulär. ∎

qwen/qwen3-235b-a22b

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Die Menge SS ergibt sich aus den Zuständen, deren Äquivalenzklasse nur aus sich selbst besteht. Aus der Tabelle aus Teilaufgabe a lässt sich ablesen:
- Zustand 2 ist zu keinem anderen Zustand äquivalent (alle Paare (2,p)(2,p) mit p≠2p \neq 2 haben ein unterscheidendes Wort).
- Zustand 5 ist ebenfalls zu keinem anderen Zustand äquivalent (alle Paare (5,p)(5,p) mit p≠5p \neq 5 unterscheiden sich bereits durch das leere Wort ε\varepsilon, da 5 ein Endzustand ist und alle anderen Zustände nicht).

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (2.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^n a^n\}  
Lcban=∅L^{cba^n}=\emptyset  
Lan={am∣0≤m≤n,m≡n(mod2)}∪{xcxRan∣x∈{a,b}∗}L^{a^n}=\{a^m \mid 0 \leq m \leq n, m \equiv n \pmod{2}\} \cup \{x c x^R a^n \mid x \in \{a,b\}^*\}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Seien i≠ji \ne j. Betrachte das Suffix s=bis = b^i. Dann gilt:
- ajs=ajbi∈La^j s = a^j b^i \in L, da j≠ij \ne i (wegen i≠ji \ne j), also s∈Lajs \in L^{a^j}.
- ais=aibi∉La^i s = a^i b^i \notin L, da i=ii = i, also s∉Lais \notin L^{a^i}.

Daher unterscheiden sich LaiL^{a^i} und LajL^{a^j} durch das Suffix ss, sind also paarweise verschieden.

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

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Aus der Äquivalenztabelle ergeben sich die Äquivalenzklassen durch die Paare, bei denen ein "=" eingetragen ist. Die Zustände 0 und 1 sind äquivalent ([0]M=[1]M={0,1}[0]_M = [1]_M = \{0,1\}), ebenso sind 3 und 4 äquivalent ([3]M=[4]M={3,4}[3]_M = [4]_M = \{3,4\}). Für die Zustände 2 und 5 ist in allen Paaren mit anderen Zuständen ein Unterscheidungswort (kein "=") eingetragen. Somit sind ihre Äquivalenzklassen einelementig: [2]M={2}[2]_M = \{2\} und [5]M={5}[5]_M = \{5\}. Die Menge SS enthält genau diese Zustände, die nur zu sich selbst äquivalent sind.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^na^n\}
Lcban=∅L^{cba^n}=\emptyset
Lan={zczRan∣z∈{a,b}∗}L^{a^n}=\{ z c z^R a^n \mid z \in \{a, b\}^* \}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Seien i,j∈Ni,j\in\N mit i≠ji\neq j. Wir betrachten das Wort x=bix = b^i.

Zunächst prüfen wir, ob x∈Lwix \in L^{w_i}:
wix=aibiw_i x = a^i b^i. Dieses Wort ist nicht in LL, da n=m=in = m = i gilt und LL nur Wörter anbma^n b^m mit n≠mn \neq m enthält. Daher ist x∉Lwix \notin L^{w_i}.

Nun prüfen wir, ob x∈Lwjx \in L^{w_j}:
wjx=ajbiw_j x = a^j b^i. Dieses Wort ist in LL, da j≠ij \neq i gilt und somit n=j≠m=in = j \neq m = i. Daher ist x∈Lwjx \in L^{w_j}.

Wir haben gezeigt, dass x∈Lwj∖Lwix \in L^{w_j} \setminus L^{w_i}. Folglich sind LwiL^{w_i} und LwjL^{w_j} für i≠ji \neq j verschieden, was bedeutet, dass die Residualsprachen {Lwn∣n∈N}\{L^{w_n} \mid n \in \N\} paarweise verschieden sind.

x-ai/grok-4

Exercise 2: Residualsprachen und Minimierung


Subproblem a (5.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): baba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Die Menge SS besteht aus den Zuständen, für die in der Äquivalenztabelle kein Eintrag „==" mit einem anderen Zustand existiert. Das bedeutet, alle Paare, die diesen Zustand mit einem anderen Zustand betreffen, enthalten ein unterscheidendes Wort und nicht „==". Aus der Tabelle ergeben sich somit die Singleton-Äquivalenzklassen für die Zustände 2 und 5, da diese nur zu sich selbst äquivalent sind.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (3.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^n a^n\}
Lcban=∅L^{cba^n}=\emptyset
Lan={y c yR an∣y∈{a,b}∗}L^{a^n}=\{y\, c\, y^R\, a^n \mid y \in \{a,b\}^*\}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Sei o.B.d.A. i<ji<j. Betrachte das Wort v:=biv:=b^i. Es gilt v∈Lwj  ⟺  j≠iv\in L^{w_j}\iff j\neq i, was wahr ist, da j>ij>i. Jedoch gilt v∉Lwi  ⟺  i≠iv\notin L^{w_i}\iff i\neq i, was falsch ist. Also ist Lwi≠LwjL^{w_i}\ne L^{w_j}.

z-ai/glm-4.5

Exercise 2: Residualsprachen und Minimierung


Subproblem a (4.0/5.0P)

Minimieren Sie den folgenden DFA MM unter Verwendung des erweiterten Minimierungsalgorithmus. Bestimmen Sie also für jedes Paar an Zuständen (q,p)(q,p), ob diese äquivalent sind. Wenn ja, tragen Sie ein Gleichheitszeichen „==" in die entsprechende Zelle ein, wenn nein, tragen Sie ein möglichst kurzes Wort ein, das dies beweist.
Zustände: 0, 1, 2, 3, 4, 5
Startzustand: 0
Finalzustände: 5
Transitionen:
    0, a -> 3
    0, b -> 2
    1, a -> 4
    1, b -> 2
    2, a -> 5
    2, b -> 4
    3, a -> 1
    3, b -> 4
    4, a -> 1
    4, b -> 4
    5, a -> 5
    5, b -> 4
Äquivalenztabelle:
(0,1): ==
(0,2): aa
(0,3): baba
(0,4): baba
(0,5): ε\varepsilon
(1,2): aa
(1,3): abaaba
(1,4): baba
(1,5): ε\varepsilon
(2,3): aa
(2,4): aa
(2,5): ε\varepsilon
(3,4): ==
(3,5): ε\varepsilon
(4,5): ε\varepsilon
1 wrong words (-1P)

Subproblem b (2.0/2.0P)

Sei QQ die Menge der Zustände von MM, also Q={0,1,2,3,4,5}Q=\{0,1,2,3,4,5\}. Bestimmen Sie S:={q∈Q:[q]M={q}}S := \{q\in Q:[q]_M=\{q\}\}, also die Menge der Zustände, die nur zu sich selbst äquivalent sind. Beschreiben Sie, wie die Menge sich aus der Tabelle ergibt.
S={2,5}S=\{2,5\}

Erklärung:
Ein Zustand qq gehört zu SS, wenn er nur zu sich selbst äquivalent ist. Das bedeutet, dass für alle anderen Zustände p≠qp \neq q der Eintrag (q,p)(q,p) in der Äquivalenztabelle nicht "==" ist. 

In der Tabelle sehen wir:
- Zustand 2 ist nicht äquivalent zu 0, 1, 3, 4 und 5.
- Zustand 5 ist nicht äquivalent zu 0, 1, 2, 3 und 4.

Alle anderen Zustände sind zu mindestens einem anderen Zustand äquivalent:
- 0 ist äquivalent zu 1
- 1 ist äquivalent zu 0
- 3 ist äquivalent zu 4
- 4 ist äquivalent zu 3

Daher sind nur die Zustände 2 und 5 nur zu sich selbst äquivalent.

Subproblem c (2.0/2.0P)

Zeichnen Sie den minimalen DFA, der L(M)L(M) erkennt. Beschriften Sie jeden Zustand mit der entsprechenden Menge an äquivalenten Zuständen aus MM.
Zustände: {0,1}, {2}, {3,4}, {5}
Startzustand: {0,1}
Finalzustände: {5}
Transitionen:
    {0,1}, a -> {3,4}
    {0,1}, b -> {2}
    {2}, a -> {5}
    {2}, b -> {3,4}
    {3,4}, a -> {0,1}
    {3,4}, b -> {3,4}
    {5}, a -> {5}
    {5}, b -> {3,4}

Subproblem d (2.0/2.0P)

Wir betrachten den folgenden DFA M′M':
Zustände: 0, 1, 2, 3, 4, 5, 6, 7
Startzustand: 0
Finalzustände: 0, 3, 7
Transitionen:
    0, a -> 1
    1, a -> 2
    2, b -> 3
    3, a -> 3
    4, b -> 5
    5, a -> 6
    6, a -> 7
    7, b -> 7
    0, b -> 4
    1, b -> 6
    2, a -> 6
    3, b -> 1
    4, a -> 4
    5, b -> 1
    6, b -> 4
    7, a -> 3
Nach Vorlesung korrespondiert jeder Zustand von M′M' zu einer Residualsprache. Geben Sie für jeden Zustand das kürzeste Wort an, das in der entsprechenden Residualsprache liegt. Falls es mehrere passende kürzeste Wörter gibt, geben Sie das alphabetisch kleinste davon an. Falls die entsprechende Residualsprache leer ist, geben Sie stattdessen „∅\emptyset" an.
0: ε\varepsilon
1: abab
2: bb
3: ε\varepsilon
4: baabaa
5: aaaa
6: aa
7: ε\varepsilon

Subproblem e (1.0/3.0P)

Sei L:={wcwR:w∈{a,b}∗}⊆{a,b,c}∗L := \{wcw^R:w \in\{a,b\}^*\}\subseteq\{a,b,c\}^*. Es gilt also z.B. c,abcba∈Lc,abcba\in L und ε,abba,abcab∉L\varepsilon,abba,abcab\notin L.

Sei n≥0n\geq 0 beliebig. Bestimmen Sie die folgenden Residualsprachen und geben Sie sie als Mengen an.
Lanbnc={bnan}L^{a^nb^nc}=\{b^na^n\}
Lcban={bc}L^{cba^n}=\{bc\}
Lan={can}L^{a^n}=\{ca^n\}

Subproblem f (4.0/4.0P)

Sei L:={anbm:n,m≥0∧n≠m}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes n∈Nn\in\N ein Wort wn∈{a,b}∗w_n\in\{a,b\}^* angeben, sodass Lw0,Lw1,...L^{w_0},L^{w_1},... paarweise verschieden sind, und beweisen Sie dies.
wn:=anw_n := a^n

Beweis Lwi≠LwjL^{w_i}\ne L^{w_j} für i,j∈N,i≠ji,j\in\N,i\ne j:
Ohne Einschränkung gelte i<ji < j. Wir zeigen, dass bi∈Lajb^i \in L^{a^j} aber bi∉Laib^i \notin L^{a^i}.

1. bi∈Lajb^i \in L^{a^j}:
   ajbi∈La^jb^i \in L da j≠ij \ne i (da i<ji < j). Nach Definition der Residualsprache gilt damit bi∈Lajb^i \in L^{a^j}.

2. bi∉Laib^i \notin L^{a^i}:
   aibi∉La^ib^i \notin L da i=ii = i. Nach Definition der Residualsprache gilt damit bi∉Laib^i \notin L^{a^i}.

Da bib^i in der einen aber nicht in der anderen Residualsprache liegt, gilt Lai≠LajL^{a^i} \ne L^{a^j}.