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:={qQ:[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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Sei i,jNi,j \in \mathbb{N} mit iji \neq j. Wir zeigen, dass LaiLajL^{a^i} \neq L^{a^j}.

Betrachte das Wort bib^i. Wir zeigen, dass biLajb^i \in L^{a^j} aber biLaib^i \notin L^{a^i}.

Behauptung 1: biLaib^i \notin L^{a^i}
Damit biLaib^i \in L^{a^i} gilt, müsste aibiLa^ib^i \in L gelten. Da L={anbm:n,m0nm}L = \{a^nb^m : n,m \geq 0 \land n \neq m\} und hier n=i=mn = i = m, gilt aibiLa^ib^i \notin L. Also ist biLaib^i \notin L^{a^i}.

Behauptung 2: biLajb^i \in L^{a^j} (für iji \neq j)
Damit biLajb^i \in L^{a^j} gilt, muss ajbiLa^jb^i \in L gelten. Da jij \neq i, ist die Bedingung nmn \neq m in der Definition von LL erfüllt, und somit gilt ajbiLa^jb^i \in L. Also ist biLajb^i \in L^{a^j}.

Da bib^i in LajL^{a^j} enthalten ist, aber nicht in LaiL^{a^i}, folgt LaiLajL^{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:={qQ:[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 pqp \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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:

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

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

Da L={akbm:k,m0,km}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 j0,m0j \geq 0, m \geq 0 sein muss, wobei n+jmn+j \neq m gelten muss.

Also: Lan={ajbm:j0,m0,n+jm}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,j1i = 0, j \geq 1
Betrachte das Wort bjb^j. 
- bjLa0b^j \in L^{a^0}, da bj=a0bjb^j = a^0 b^j und 0j0 \neq j (für j1j \geq 1)
- bjLajb^j \notin L^{a^j}, da für bj=akbmb^j = a^k b^m mit j+kmj+k \neq m folgt k=0,m=jk=0, m=j, also j+0jj+0 \neq j, was falsch ist

Daher La0LajL^{a^0} \neq L^{a^j} für alle j1j \geq 1.

Fall 2: i,j1,iji,j \geq 1, i \neq j
Betrachte das Wort bib^i.
- biLajb^i \in L^{a^j}, da bi=a0bib^i = a^0 b^i und j+0=jij+0 = j \neq i (da iji \neq j)
- biLaib^i \notin L^{a^i}, da für bi=akbmb^i = a^k b^m mit i+kmi+k \neq m folgt k=0,m=ik=0, m=i, also i+0ii+0 \neq i, was falsch ist

Daher LaiLajL^{a^i} \neq L^{a^j} für alle ij1i \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:={qQ:[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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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={ycyRany{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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i} \ne L^{w_j} für i,jN,iji,j \in \mathbb{N}, i \ne j:
Sei iji \ne j. Betrachte das Wort bib^i. Da iji \ne j gilt, ist ajbiLa^j b^i \in L, weil die Anzahl der a's jj und der b's ii ist und jij \ne i. Thus, biLajb^i \in L^{a^j}. however, aibiLa^i b^i \notin L, weil i=ii = i, also biLaib^i \notin L^{a^i}. Daher ist LaiLajL^{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:={qQ:[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 pqp \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 pqp \neq q als äquivalent markiert ist:
- Zustand 2: Alle Paare (2,p)(2,p) für p2p \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 p5p \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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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={vcvRanv{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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Seien i,jNi, j \in \mathbb{N} mit iji \neq j beliebig. Betrachte das Wort z=bjz = b^j.  
- zLwiz \in L^{w_i}, denn wiz=aibjLw_i z = a^i b^j \in L (da iji \neq j).  
- zLwjz \notin L^{w_j}, denn wjz=ajbjLw_j z = a^j b^j \notin L (da j=jj = j).  
Somit gilt LwiLwjL^{w_i} \neq L^{w_j}, da zz die Sprachen trennt.  
Da i,ji, j beliebig mit iji \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:={qQ:[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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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={wcwRanw{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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Seien i,jNi, j \in \mathbb{N} mit iji \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}uvL}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 akvL={anbmn,m0nm}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 m0m \ge 0 sein.
Die Bedingung nmn \ne m wird dann zu kmk \ne m.
Also ist die Residualsprache Lak={bmm0mk}L^{a^k} = \{b^m \mid m \ge 0 \land m \ne k\}.

Um zu beweisen, dass LaiLajL^{a^i} \ne L^{a^j} für iji \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 zLaiz \in L^{a^i}:
Das Wort z=biz=b^i liegt in Lai={bmm0mi}L^{a^i} = \{b^m \mid m \ge 0 \land m \ne i\} genau dann, wenn m=im=i die Bedingung mim \ne i erfüllt. Dies ist offensichtlich falsch. Also biLaib^i \notin L^{a^i}.

- Wir prüfen, ob zLajz \in L^{a^j}:
Das Wort z=biz=b^i liegt in Laj={bmm0mj}L^{a^j} = \{b^m \mid m \ge 0 \land m \ne j\} genau dann, wenn m=im=i die Bedingung mjm \ne j erfüllt. Da wir iji \ne j angenommen haben, ist diese Bedingung wahr. Also biLajb^i \in L^{a^j}.

Da wir ein Wort z=biz=b^i gefunden haben, für das zLajz \in L^{a^j} und zLaiz \notin L^{a^i} gilt, sind die beiden Residualsprachen verschieden. Da dies für jedes Paar iji \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:={qQ:[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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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={wcwRanw{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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Sei iji\neq j beliebig und setze x:=bix:=b^i. Dann gilt
- aix=aibiLa^i x = a^i b^i \notin L, da die Anzahlen von aa und bb gleich sind. Also xLaix\notin L^{a^i}.
- ajx=ajbiLa^j x = a^j b^i \in L, da ajbia^j b^i die Form anbma^n b^m hat und wegen jij\neq i auch nmn\neq m. Also xLajx\in L^{a^j}.

Damit ist LaiLajL^{a^i}\neq L^{a^j} für alle iji\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:={qQ:[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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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={vcvRanv{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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\mathbb{N},\,i\ne j:

Für ein festes kNk\in\mathbb{N} betrachten wir das Residuum nach dem Präfix aka^{k}:
Lak={x{a,b}akxL}.
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:

akbmL    km.
a^{k}b^{m}\in L 
\iff k\neq m .


Damit

Lak={bmmN, mk}.(1)
L^{a^{k}} = \{\,b^{m}\mid m\in\mathbb{N},\ m\neq k\,\}.
\tag{1}


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

* Nach (1) ist biLaib^{i}\notin L^{a^{i}}, weil dort genau das Wort bib^{i} fehlt (es erfüllt m=im=i).
* Ebenfalls nach (1) ist biLajb^{i}\in L^{a^{j}}, weil iji\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
LaiLaj.
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:={qQ:[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 p2p \neq 2 haben ein unterscheidendes Wort).
- Zustand 5 ist ebenfalls zu keinem anderen Zustand äquivalent (alle Paare (5,p)(5,p) mit p5p \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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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={am0mn,mn(mod2)}{xcxRanx{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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Seien iji \ne j. Betrachte das Suffix s=bis = b^i. Dann gilt:
- ajs=ajbiLa^j s = a^j b^i \in L, da jij \ne i (wegen iji \ne j), also sLajs \in L^{a^j}.
- ais=aibiLa^i s = a^i b^i \notin L, da i=ii = i, also sLais \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:={qQ:[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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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={zczRanz{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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Seien i,jNi,j\in\N mit iji\neq j. Wir betrachten das Wort x=bix = b^i.

Zunächst prüfen wir, ob xLwix \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 nmn \neq m enthält. Daher ist xLwix \notin L^{w_i}.

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

Wir haben gezeigt, dass xLwjLwix \in L^{w_j} \setminus L^{w_i}. Folglich sind LwiL^{w_i} und LwjL^{w_j} für iji \neq j verschieden, was bedeutet, dass die Residualsprachen {LwnnN}\{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:={qQ:[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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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={ycyRany{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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Sei o.B.d.A. i<ji<j. Betrachte das Wort v:=biv:=b^i. Es gilt vLwj    jiv\in L^{w_j}\iff j\neq i, was wahr ist, da j>ij>i. Jedoch gilt vLwi    iiv\notin L^{w_i}\iff i\neq i, was falsch ist. Also ist LwiLwjL^{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:={qQ:[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 pqp \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 MM':
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 MM' 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,abcbaLc,abcba\in L und ε,abba,abcabL\varepsilon,abba,abcab\notin L.

Sei n0n\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,m0nm}L := \{a^nb^m:n,m\ge0\wedge n\ne m\}. Zeigen Sie, dass LL nicht regulär ist, indem Sie für jedes nNn\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 LwiLwjL^{w_i}\ne L^{w_j} für i,jN,iji,j\in\N,i\ne j:
Ohne Einschränkung gelte i<ji < j. Wir zeigen, dass biLajb^i \in L^{a^j} aber biLaib^i \notin L^{a^i}.

1. biLajb^i \in L^{a^j}:
   ajbiLa^jb^i \in L da jij \ne i (da i<ji < j). Nach Definition der Residualsprache gilt damit biLajb^i \in L^{a^j}.

2. biLaib^i \notin L^{a^i}:
   aibiLa^ib^i \notin L da i=ii = i. Nach Definition der Residualsprache gilt damit biLaib^i \notin L^{a^i}.

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