anthropic/claude-opus-4.1

Exercise 2: DFA-Algorithmen


Subproblem a (6.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, b -> q3
    q2, a -> q5
    q3, b -> q3
    q3, a -> q7
    q7, a -> q7
    q7, b -> q7
    q5, b -> q4
    q5, a -> q6
    q6, a -> q5
    q6, b -> q7
    q4, a -> q4
    q4, b -> q4
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 0, 1, 2, 3
    q4: \emptyset
    q5: 3
    q6: 1, 2
    q7: 1, 2, 3

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
M ist nicht minimal. Die Zustände q2 und q6 sind äquivalent, da sie beide auf 'a' nach q5 gehen und auf 'b' zu äquivalenten Zuständen (q3 bzw. q7) übergehen. Ebenso sind q3 und q7 äquivalent, da beide auf 'a' nach q7 gehen und auf 'b' Selbstschleifen haben (q3→q3 bzw. q7→q7). Diese Paare von äquivalenten Zuständen können jeweils zu einem Zustand verschmolzen werden, wodurch ein minimaler DFA mit 6 statt 8 Zuständen entsteht.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0, 0), (1, 2), (2, 1), (2, 2), (2, 0)
Startzustand: (0, 0)
Finalzustände: (1, 2), (2, 1), (2, 2)
Transitionen:
(0, 0), a -> (1, 2)
(0, 0), b -> (0, 0)
(1, 2), a -> (2, 1)
(1, 2), b -> (2, 2)
(2, 1), a -> (2, 2)
(2, 1), b -> (2, 0)
(2, 2), a -> (2, 1)
(2, 2), b -> (2, 2)
(2, 0), a -> (2, 2)
(2, 0), b -> (2, 0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:
Algorithmus zur Konstruktion von MM':

Gegeben sei ein DFA M=(Q,{a,b,c},δ,q0,F)M = (Q, \{a,b,c\}, \delta, q_0, F) mit nn Zuständen.

1. Konstruiere einen NFA mit ε\varepsilon-Transitionen: Erstelle einen NFA N=(Q,{a,b},δ,q0,F)N = (Q, \{a,b\}, \delta', q_0, F) mit:
   - Denselben Zuständen wie MM
   - Für jede Transition δ(q,a)=q\delta(q, a) = q' mit a{a,b}a \in \{a,b\}: füge (q,a,q)(q, a, q') zu δ\delta' hinzu
   - Für jede Transition δ(q,c)=q\delta(q, c) = q': füge (q,ε,q)(q, \varepsilon, q') zu δ\delta' hinzu

2. Entferne ε\varepsilon-Transitionen: Berechne für jeden Zustand qq die ε\varepsilon-Hülle ε-closure(q)\varepsilon\text{-closure}(q). Erstelle einen NFA ohne ε\varepsilon-Transitionen, indem für jede Transition (q,a,p)(q, a, p) mit a{a,b}a \in \{a,b\} und jeden Zustand rε-closure(p)r \in \varepsilon\text{-closure}(p) eine Transition (q,a,r)(q, a, r) hinzugefügt wird. Die Finalzustände sind alle Zustände qq, deren ε\varepsilon-Hülle mindestens einen ursprünglichen Finalzustand enthält.

3. Potenzmengenkonstruktion: Konvertiere den resultierenden NFA zu einem DFA MM' mittels Potenzmengenkonstruktion.

Begründung für die Schranke f(n)=2nf(n) = 2^n:

Der konstruierte NFA hat dieselben nn Zustände wie der ursprüngliche DFA MM. Bei der Potenzmengenkonstruktion entspricht jeder Zustand des resultierenden DFA einer Teilmenge der NFA-Zustände. Da es maximal 2n2^n verschiedene Teilmengen von nn Zuständen gibt, hat der resultierende DFA MM' höchstens 2n2^n Zustände.

Die Korrektheit folgt daraus, dass ein Wort w{a,b}w \in \{a,b\}^* genau dann von MM' akzeptiert wird, wenn es ein Wort v{a,b,c}v \in \{a,b,c\}^* gibt mit w=Rc(v)w = R_c(v) und vL(M)v \in L(M).

anthropic/claude-sonnet-4

Exercise 2: DFA-Algorithmen


Subproblem a (0.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q4, q5, q6
Transitionen:
    q0, a -> q7
    q0, b -> q1
    q1, a -> q7
    q1, b -> q2
    q2, a -> q3
    q2, b -> q4
    q3, a -> q5
    q3, b -> q7
    q4, a -> q6
    q4, b -> q4
    q5, a -> q3
    q5, b -> q6
    q6, a -> q6
    q6, b -> q6
    q7, a -> q7
    q7, b -> q7
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 3
    q4: 0, 1, 2, 3
    q5: 1, 2
    q6: 1, 2, 3
    q7: \emptyset
wrong final states (-1P)
11 wrong transitions (-6P)
wrong state sets for [3, 4, 5, 6, 7] (-3P)

Subproblem b (0.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
wrong answer for choice (0)
The DFA M is minimal because no two states are equivalent. Each state has a unique transition pattern - either they differ in finality (q7 vs all others) or they have different transitions for at least one input symbol among the final states.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0, 0), (1, 2), (2, 1), (2, 2), (2, 0)
Startzustand: (0, 0)
Finalzustände: (1, 2), (2, 1), (2, 2)
Transitionen:
(0, 0), a -> (1, 2)
(0, 0), b -> (0, 0)
(1, 2), a -> (2, 1)
(1, 2), b -> (2, 2)
(2, 1), a -> (2, 2)
(2, 1), b -> (2, 0)
(2, 2), a -> (2, 1)
(2, 2), b -> (2, 2)
(2, 0), a -> (2, 2)
(2, 0), b -> (2, 0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:

Algorithmus:
1. Definiere für jede Menge S von Zuständen die c-Hülle: c-closure(S) = {q | q ist von einem Zustand in S durch eine Folge von c-Transitionen erreichbar}

2. Die Zustände von M' sind Teilmengen der Zustände von M. Der Startzustand ist c-closure({q₀}), wobei q₀ der Startzustand von M ist.

3. Für jeden Zustand S von M' und jedes Symbol a ∈ {a,b} ist die Transition: δ'(S,a) = c-closure({δ(q,a) | q ∈ S und δ(q,a) ist definiert})

4. Ein Zustand S ist final in M', wenn S mindestens einen Finalzustand von M enthält.

5. Konstruiere nur die erreichbaren Zustände.

Begründung für f(n) = 2^n:
Jeder Zustand von M' entspricht einer Teilmenge der Zustände von M. Da M genau n Zustände hat, gibt es höchstens 2^n verschiedene Teilmengen und damit höchstens 2^n Zustände in M'. Die Konstruktion ist eine Verallgemeinerung der Teilmengenkonstruktion: Wir verfolgen simultan alle möglichen Läufe von M auf Wörtern, die durch Einfügen beliebiger c-Zeichen aus dem aktuell gelesenen Präfix entstehen können.

Diese Schranke ist scharf erreichbar, da in pathologischen Fällen tatsächlich alle 2^n Teilmengen als Zustände benötigt werden können.

deepseek/deepseek-chat-v3.1

Exercise 2: DFA-Algorithmen


Subproblem a (6.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, a -> q4
    q0, b -> q1
    q1, a -> q4
    q1, b -> q2
    q2, a -> q5
    q2, b -> q3
    q3, a -> q7
    q3, b -> q3
    q4, a -> q4
    q4, b -> q4
    q5, a -> q6
    q5, b -> q4
    q6, a -> q5
    q6, b -> q7
    q7, a -> q7
    q7, b -> q7
Zustandstabelle:
    q0: \{0\}
    q1: \{0,1\}
    q2: \{0,1,2\}
    q3: \{0,1,2,3\}
    q4: \emptyset
    q5: \{3\}
    q6: \{1,2\}
    q7: \{1,2,3\}

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
M ist nicht minimal, da die Zustände q3 und q7 äquivalent sind. Both accept all strings over the alphabet, as from q3, transitions on a lead to q7 and on b lead to q3, both of which are final and accept all strings, and from q7, all transitions lead to itself, which is final and accepts all strings. Therefore, they can be merged, indicating that M is not minimal.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0,0), (1,2), (2,1), (2,2), (2,0)
Startzustand: (0,0)
Finalzustände: (1,2), (2,1), (2,2)
Transitionen:
(0,0), a -> (1,2)
(0,0), b -> (0,0)
(1,2), a -> (2,1)
(1,2), b -> (2,2)
(2,1), a -> (2,2)
(2,1), b -> (2,0)
(2,2), a -> (2,1)
(2,2), b -> (2,2)
(2,0), a -> (2,2)
(2,0), b -> (2,0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:
Um den DFA MM' für Rc(L(M))R_c(L(M)) zu konstruieren, wird der folgende Algorithmus verwendet:
1. Berechne für jeden Zustand qq des DFA MM die cc-Abschlussmenge ccl(q)\text{ccl}(q), die alle Zustände enthält, die von qq aus durch beliebig viele cc-Transitionen erreichbar sind. Da MM ein DFA ist, ist die cc-Transition deterministisch, und ccl(q)\text{ccl}(q) kann durch Iteration der cc-Transitionen berechnet werden und hat höchstens nn Zustände.
2. Der DFA MM' wird durch Potenzmengenkonstruktion aus einem NFA gebildet. Die Zustände von MM' sind Teilmengen der Zustände von MM. Der Startzustand ist ccl(s)\text{ccl}(s), wobei ss der Startzustand von MM ist.
3. Für jede Zustandsmenge SQS \subseteq Q und jedes Symbol σ{a,b}\sigma \in \{a,b\} ist die Transition definiert als δ(S,σ)=qSccl(δ(q,σ))\delta'(S, \sigma) = \bigcup_{q \in S} \text{ccl}(\delta(q, \sigma)).
4. Ein Zustand SS ist final in MM', wenn SS einen Finalzustand von MM enthält.
Da die Anzahl der Teilmengen von QQ höchstens 2n2^n ist, hat MM' höchstens 2n2^n Zustände. Diese obere Schranke ist scharf, da im Worst-Case alle Teilmengen erreichbar sein können.

deepseek/deepseek-r1-0528

Exercise 2: DFA-Algorithmen


Subproblem a (0.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5
Transitionen:
    q0, a -> q4
    q0, b -> q1
    q1, a -> q4
    q1, b -> q2
    q2, a -> q3
    q2, b -> q2
    q3, a -> q5
    q3, b -> q4
    q4, a -> q4
    q4, b -> q4
    q5, a -> q3
    q5, b -> q5
    q6, a -> q6
    q6, b -> q6
    q7, a -> q7
    q7, b -> q7
Zustandstabelle:
    q0: \{0\}
    q1: \{0,1\}
    q2: \{0,1,2\}
    q3: \{3\}
    q4: \emptyset
    q5: \{1,2\}
    q6: \emptyset
    q7: \emptyset
wrong final states (-1P)
8 wrong transitions (-4P)
wrong state sets for [3, 5, 6, 7] (-2P)

Subproblem b (0.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
The DFA MM is not minimal because it contains equivalent states. Specifically:  
- States q2q_2 and q5q_5 are equivalent (both represent sets containing final state 22 from NN, and their transitions yield identical behavior).  
- States q4q_4, q6q_6, and q7q_7 are equivalent (all represent the empty set \emptyset, acting as non-final sinks).  
Merging these states would reduce MM to a smaller equivalent DFA.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0,0), (1,2), (2,1), (2,2), (2,0)
Startzustand: (0,0)
Finalzustände: (1,2), (2,1), (2,2)
Transitionen:
    (0,0), a -> (1,2)
    (0,0), b -> (0,0)
    (1,2), a -> (2,1)
    (1,2), b -> (2,2)
    (2,1), a -> (2,2)
    (2,1), b -> (2,0)
    (2,2), a -> (2,1)
    (2,2), b -> (2,2)
    (2,0), a -> (2,2)
    (2,0), b -> (2,0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:
Um den DFA MM' für Rc(L(M))R_c(L(M)) zu konstruieren, wird folgender Algorithmus verwendet:
1. Berechne für jeden Zustand qq in MM die ε\varepsilon-Hülle bzgl. cc: \textscECLOSE(q)\textsc{ECLOSE}(q) = alle durch cc-Übergänge von qq erreichbaren Zustände.
2. Erstelle einen NFA NN mit denselben Zuständen wie MM, Startzustand q0q_0 und Finalzustandsmenge FF. Die Übergänge für a,ba,b sind:
  δN(q,σ)=r\textscECLOSE(q)\textscECLOSE(δ(r,σ))\delta_N(q, \sigma) = \bigcup_{r \in \textsc{ECLOSE}(q)} \textsc{ECLOSE}\big( \delta(r,\sigma) \big) für σ{a,b}\sigma \in \{a,b\}.
3. Wende Potenzmengenkonstruktion auf NN an, um MM' zu erhalten: Zustände sind Teilmengen von QQ (der Zustände von MM).

Da MM nn Zustände hat, gibt es höchstens 2n2^n Teilmengen. Somit hat MM' maximal 2n2^n Zustände.

google/gemini-2.5-pro

Exercise 2: DFA-Algorithmen


Subproblem a (6.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, b -> q3
    q2, a -> q5
    q3, b -> q3
    q3, a -> q7
    q7, a -> q7
    q7, b -> q7
    q5, b -> q4
    q5, a -> q6
    q6, a -> q5
    q6, b -> q7
    q4, a -> q4
    q4, b -> q4
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 0, 1, 2, 3
    q4: \emptyset
    q5: 3
    q6: 1, 2
    q7: 1, 2, 3

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
Nein. Der Automat ist nicht minimal, da er äquivalente Zustände enthält.
Zum Beispiel sind die Zustände q2q_2 und q6q_6 äquivalent.
Beide sind Endzustände.
- Bei Eingabe 'a' gehen beide in den Zustand q5q_5 über: δ(q2,a)=q5\delta(q_2, a) = q_5 und δ(q6,a)=q5\delta(q_6, a) = q_5.
- Bei Eingabe 'b' geht q2q_2 in q3q_3 über und q6q_6 in q7q_7. Die Zustände q3q_3 und q7q_7 sind ebenfalls äquivalent, da von beiden Zuständen aus jedes beliebige Wort w{a,b}w \in \{a,b\}^* zu einem Endzustand führt und somit akzeptiert wird.

Da es mindestens ein Paar äquivalenter Zustände gibt, ist der DFA nicht minimal.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0, 0), (1, 2), (2, 0), (2, 1), (2, 2)
Startzustand: (0, 0)
Finalzustände: (1, 2), (2, 1), (2, 2)
Transitionen:
(0, 0), a -> (1, 2)
(0, 0), b -> (0, 0)
(1, 2), a -> (2, 1)
(1, 2), b -> (2, 2)
(2, 0), a -> (2, 2)
(2, 0), b -> (2, 0)
(2, 1), a -> (2, 2)
(2, 1), b -> (2, 0)
(2, 2), a -> (2, 1)
(2, 2), b -> (2, 2)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): a
L(M1)L(M2)L(M_1)\setminus L(M_2): aab
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:
Die Sprache Rc(L(M))R_c(L(M)) ist das homomorphe Bild von L(M)L(M) unter dem Homomorphismus h:{a,b,c}{a,b}h:\{a,b,c\}^* \rightarrow \{a,b\}^*, der wie folgt definiert ist: h(a)=ah(a)=a, h(b)=bh(b)=b und h(c)=εh(c)=\varepsilon. Da reguläre Sprachen unter Homomorphismen abgeschlossen sind, ist Rc(L(M))R_c(L(M)) ebenfalls regulär und es gibt einen DFA MM', der sie erkennt.

Algorithmus zur Konstruktion von M':

Sei M=(Q,{a,b,c},δ,q0,F)M=(Q, \{a,b,c\}, \delta, q_0, F) der gegebene DFA mit n=Qn=|Q| Zuständen. Wir konstruieren einen neuen DFA M=(Q,{a,b},δ,q0,F)M'=(Q', \{a,b\}, \delta', q'_0, F') wie folgt:

1.  Konstruiere einen NFA mit ε\varepsilon-Transitionen (NεN_\varepsilon):
    Wir interpretieren den DFA MM als einen NFA mit ε\varepsilon-Transitionen, NεN_\varepsilon, über dem Alphabet {a,b}\{a,b\}. Die Zustände, der Startzustand und die Endzustände bleiben gleich. Die Transitionen werden wie folgt modifiziert:
    - Für jede Transition δ(q,x)=p\delta(q, x) = p in MM mit x{a,b}x \in \{a,b\}, fügen wir eine Transition (q,x,p)(q, x, p) zu NεN_\varepsilon hinzu.
    - Für jede Transition δ(q,c)=p\delta(q, c) = p in MM, fügen wir eine ε\varepsilon-Transition (q,ε,p)(q, \varepsilon, p) zu NεN_\varepsilon hinzu.
    Dieser NεN_\varepsilon hat nn Zustände und erkennt die Sprache Rc(L(M))R_c(L(M)).

2.  Konvertiere NεN_\varepsilon zu einem DFA MM' via Potenzmengenkonstruktion:
    Wir wenden die Standard-Potenzmengenkonstruktion an, um NεN_\varepsilon in einen äquivalenten DFA MM' umzuwandeln.
    - Zustände von M': Die Zustände von MM' sind Teilmengen der Zustände von NεN_\varepsilon (und damit von MM). Also QP(Q)Q' \subseteq \mathcal{P}(Q).
    - Startzustand von M': Der Startzustand q0q'_0 ist die ε\varepsilon-Hülle des ursprünglichen Startzustands, d.h. q0=E({q0})={qQq ist von q0 in Nε durch ε-Transitionen erreichbar}q'_0 = E(\{q_0\}) = \{q \in Q \mid q \text{ ist von } q_0 \text{ in } N_\varepsilon \text{ durch } \varepsilon\text{-Transitionen erreichbar}\}.
    - Transitionen von M': Für einen Zustand SQS \in Q' und ein Zeichen x{a,b}x \in \{a,b\} wird die Nachfolgezustand δ(S,x)\delta'(S,x) wie folgt berechnet:
        1.  Bestimme die Menge aller Zustände, die von einem Zustand in SS durch eine xx-Transition erreicht werden: Sx=qS{p(q,x,p) ist eine Transition in Nε}S_x = \bigcup_{q \in S} \{ p \mid (q,x,p) \text{ ist eine Transition in } N_\varepsilon \}.
        2.  Bestimme die ε\varepsilon-Hülle dieser Menge: δ(S,x)=E(Sx)=pSxE({p})\delta'(S,x) = E(S_x) = \bigcup_{p \in S_x} E(\{p\}).
    - Endzustände von M': Ein Zustand SQS \in Q' ist ein Endzustand, wenn er mindestens einen der ursprünglichen Endzustände enthält, d.h. F={SQSF}F' = \{S \in Q' \mid S \cap F \neq \emptyset\}.
    Es werden nur die von q0q'_0 aus erreichbaren Zustände konstruiert.

Argumentation zur Zustandszahl:

Der beschriebene Algorithmus konstruiert einen DFA MM', dessen Zustände Teilmengen des Zustandsraums QQ des ursprünglichen DFA MM sind.
Da MM per Definition nn Zustände hat (Q=n|Q|=n), gibt es P(Q)=2n|\mathcal{P}(Q)| = 2^n mögliche Teilmengen von QQ.
Somit kann der resultierende DFA MM' höchstens 2n2^n Zustände haben. Unsere Wahl f(n)=2nf(n)=2^n ist also eine gültige obere Schranke für die Anzahl der Zustände von MM'.

openai/gpt-5

Exercise 2: DFA-Algorithmen


Subproblem a (6.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, b -> q3
    q2, a -> q5
    q3, b -> q3
    q3, a -> q7
    q7, a -> q7
    q7, b -> q7
    q5, b -> q4
    q5, a -> q6
    q6, a -> q5
    q6, b -> q7
    q4, a -> q4
    q4, b -> q4
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 0, 1, 2, 3
    q4: \emptyset
    q5: 3
    q6: 1, 2
    q7: 1, 2, 3

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
Nein. q3 und q7 sind äquivalent (beide akzeptieren jede Fortsetzung, also Σ*), ebenso q2 und q6 (sie unterscheiden sich nur durch Übergänge zu q3 bzw. q7, die äquivalent sind). Diese Paare können zusammengelegt werden; M ist daher nicht minimal.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0, 0), (1, 2), (2, 1), (2, 2), (2, 0)
Startzustand: (0, 0)
Finalzustände: (1, 2), (2, 1), (2, 2)
Transitionen:
(0, 0), a -> (1, 2)
(0, 0), b -> (0, 0)
(1, 2), a -> (2, 1)
(1, 2), b -> (2, 2)
(2, 1), a -> (2, 2)
(2, 1), b -> (2, 0)
(2, 2), a -> (2, 1)
(2, 2), b -> (2, 2)
(2, 0), a -> (2, 2)
(2, 0), b -> (2, 0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^{n}
Begründung:
- Idee: Behandle cc-Transitionen als ε\varepsilon-Transitionen. Erhalte so einen ε\varepsilon-NFA NN über dem Alphabet {a,b}\{a,b\}, der genau dann ein Wort w{a,b}w\in\{a,b\}^* akzeptiert, wenn es in MM eine Ausführung gibt, in der man zwischen den a/ba/b-Symbolen beliebig viele cc einfügt (also genau die Wörter in Rc(L(M))R_c(L(M))).

- Konstruktion:
  1) Gegeben M=(Q,{a,b,c},δ,q0,F)M=(Q,\{a,b,c\},\delta,q_0,F), berechne für jedes qQq\in Q die cc-Abschlussmenge C(q)={pQqcp}C(q)=\{p\in Q\mid q\xrightarrow{c^*}p\} (Transitiv-reflexiver Abschluss entlang der cc-Kanten).
  2) Definiere einen ε\varepsilon-NFA NN über {a,b}\{a,b\} mit Zustandsmenge QQ, Startmenge C(q0)C(q_0), und für x{a,b}x\in\{a,b\} die Übergänge SxC(δ(S,x))S \xrightarrow{x} C\big(\delta(S,x)\big), wobei δ(S,x)=sS{δ(s,x)}\delta(S,x)=\bigcup_{s\in S}\{\delta(s,x)\} und C(S)=sSC(s)C(S)=\bigcup_{s\in S}C(s). Akzeptierende Zustände sind die mit C(S)FC(S)\cap F\neq\emptyset (da wir den cc-Abschluss nach jedem Schritt nehmen, äquivalent: aktueller SS schneidet FF).
  3) Wende auf NN die Potenzmengenkonstruktion an, beginnend bei S0=C(q0)S_0=C(q_0) und mit Übergängen SxC(δ(S,x))S\xrightarrow{x}C(\delta(S,x)) für x{a,b}x\in\{a,b\}. Die so erreichten Teilmengen sind die Zustände von MM', akzeptierend sind die SS mit SFS\cap F\neq\emptyset.

- Korrektheit: Das Ersetzen der cc-Kanten durch ε\varepsilon-Kanten simuliert genau das Löschen der cc-Symbole, d.h. L(N)=Rc(L(M))L(N)=R_c(L(M)). Die Potenzmengenkonstruktion liefert einen äquivalenten DFA MM' mit L(M)=L(N)L(M')=L(N).

- Zustandsanzahl: Alle in der Konstruktion entstehenden Zustände sind Teilmengen von QQ; somit gibt es höchstens 2n2^n Zustände. Dieser Bound ist im Worst Case tight (z.B. wenn alle cc-Kanten Schleifen sind, so dass keine Reduktion durch cc-Abschlüsse entsteht).

openai/gpt-oss-120b

Exercise 2: DFA-Algorithmen


Subproblem a (6.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, a -> q4
    q0, b -> q1
    q1, a -> q4
    q1, b -> q2
    q2, a -> q5
    q2, b -> q3
    q3, a -> q7
    q3, b -> q3
    q4, a -> q4
    q4, b -> q4
    q5, a -> q6
    q5, b -> q4
    q6, a -> q5
    q6, b -> q7
    q7, a -> q7
    q7, b -> q7
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 0, 1, 2, 3
    q4: \emptyset
    q5: 3
    q6: 1, 2
    q7: 1, 2, 3

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
The DFA is not minimal.  In the reachable part of M the following states are equivalent:
- q₂ and q₆ have identical future behaviour,
- q₃ and q₇ have identical future behaviour.

Merging each pair yields a smaller DFA, therefore the original DFA M is not minimal.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0,0), (1,2), (2,1), (2,2), (2,0)
Startzustand: (0,0)
Finalzustände: (1,2), (2,1), (2,2)
Transitionen:
(0,0), a -> (1,2)
(0,0), b -> (0,0)
(1,2), a -> (2,1)
(1,2), b -> (2,2)
(2,1), a -> (2,2)
(2,1), b -> (2,0)
(2,2), a -> (2,1)
(2,2), b -> (2,2)
(2,0), a -> (2,2)
(2,0), b -> (2,0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa  
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab  
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (0.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n)=n+1f(n)=n+1

Begründung:<br>
Gegeben ein DFA  
M=(Q,{a,b,c},δ,q0,F)M=(Q,\{a,b,c\},\delta,q_{0},F) mit Q=n|Q|=n.

1. c‑Closure berechnen  
   Für jeden Zustand qQq\in Q bestimmen wir die Menge  
   C(q)={pQqcp},
   C(q)=\{p\in Q \mid q \xrightarrow{c^{*}} p\},
   
   also alle Zustände, die von qq über beliebig viele c‑Übergänge (auch 0) erreichbar sind.  
   Da die c‑Übergänge allein einen gerichteten Graphen bilden, lässt sich C(q)C(q) für alle qq in Zeit O(n2)O(n^{2}) mittels einer Tiefensuche bzw. Floyd‑Warshall ermitteln.

2. DFA ohne c‑Eingaben konstruieren  
   Wir definieren einen neuen Automaten  
   M=(Q{qsink},{a,b},δ,q0,F)
   M'=(Q\cup\{q_{\text{sink}}\},\{a,b\},\delta',q_{0},F')
   
   mit den gleichen Zuständen wie MM (plus einem einzigen Fehlzustand qsinkq_{\text{sink}}, falls ein Übergang nicht definiert ist).

   * Übergangsfunktion  
     Für x{a,b}x\in\{a,b\} und qQq\in Q setzen wir
     δ(q,x)={ein beliebiger Zustand pC(δ(q,x))wenn δ(q,x) definiert ist,qsinksonst.
     \delta'(q,x)=
     \begin{cases}
        \text{ein beliebiger Zustand } p\in C(\delta(q,x)) & \text{wenn }\delta(q,x)\text{ definiert ist},\\[4pt]
        q_{\text{sink}} & \text{sonst}.
     \end{cases}
     
     Das bedeutet: wir führen zunächst den normalen xx-Übergang von MM aus und „überspringen“ danach beliebig viele c‑Übergänge, indem wir sofort in die entsprechende c‑Closure gehen.

   * Endzustände  
     Ein Zustand qq ist Endzustand von MM', genau dann wenn die c‑Closure von qq einen Endzustand von MM enthält:
     F={qQC(q)F}    {qsink  :  qsinkF}.
     F'=\{\,q\in Q \mid C(q)\cap F\neq\emptyset\,\}\;\cup\;\{q_{\text{sink}}\;:\;q_{\text{sink}}\in F\}.
     

3. Korrektheit  
   Für ein Wort w{a,b}w\in\{a,b\}^{*} lässt sich ein Wort w^{a,b,c}\hat w\in\{a,b,c\}^{*} mit Rc(w^)=wR_{c}(\hat w)=w exakt dann erzeugen, wenn man in MM von q0q_{0} aus die Buchstaben von ww liest und zwischendurch beliebig viele c‑Übergänge ausführt.  Durch die Definition von δ\delta' und FF' akzeptiert MM' genau die Wörter, für die ein solches w^\hat w existiert; also
   L(M)=Rc(L(M)).
   L(M') = R_{c}\bigl(L(M)\bigr).
   

4. Zustandsanzahl  
   Der konstruierte Automat verwendet höchstens die ursprünglichen nn Zustände von MM plus ggf. einen zusätzlichen Fehlzustand, also höchstens n+1n+1 Zustände.  Damit erfüllt er die geforderte Schranke f(n)=n+1f(n)=n+1.

Der beschriebene Algorithmus läuft in polynomialer Zeit (O(n²) für die Closure‑Berechnung und O(n) für das Anlegen der neuen Übergänge) und liefert einen DFA MM' mit f(n)=n+1\le f(n)=n+1 Zuständen, der exakt die Sprache Rc(L(M))R_{c}(L(M)) akzeptiert.

qwen/qwen3-235b-a22b

Exercise 2: DFA-Algorithmen


Subproblem a (1.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, a -> q3
    q2, b -> q5
    q3, a -> q6
    q3, b -> q4
    q4, a -> q4
    q4, b -> q4
    q5, a -> q7
    q5, b -> q5
    q6, a -> q3
    q6, b -> q7
    q7, a -> q7
    q7, b -> q7
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 3
    q4: \emptyset
    q5: 0, 1, 2, 3
    q6: 1, 2
    q7: 1, 2, 3
7 wrong transitions (-4P)
wrong state sets for [3, 5] (-1P)

Subproblem b (0.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
Nein, M ist nicht minimal, da der Potenzmengenalgorithmus lediglich einen äquivalenten DFA erzeugt, aber nicht zwingend den minimalen DFA. Zustände wie q5 und q6 könnten beispielsweise unter bestimmten Eingaben identische Sprachverhalten aufweisen und somit zusammengefasst werden können, was Redundanzen aufzeigt.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0, 0), (1, 2), (2, 1), (2, 2), (2, 0)  
Startzustand: (0, 0)  
Finalzustände: (1, 2), (2, 1), (2, 2)  
Transitionen:  
(0, 0), a -> (1, 2)  
(0, 0), b -> (0, 0)  
(1, 2), a -> (2, 1)  
(1, 2), b -> (2, 2)  
(2, 1), a -> (2, 2)  
(2, 1), b -> (2, 0)  
(2, 2), a -> (2, 1)  
(2, 2), b -> (2, 2)  
(2, 0), a -> (2, 2)  
(2, 0), b -> (2, 0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa  
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab  
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n

Begründung:
Um MM' zu konstruieren, ersetzen wir in MM alle cc-Transitions durch ε-Transitionen und eliminieren diese durch ε-closure-Bildung. Danach wenden wir die Potenzmengenkonstruktion an. Jeder Zustand in MM' repräsentiert eine Teilmenge aller Zustände aus MM, da cc-freie Übergänge zu beliebigen Kombinationen führen können. Dies ergibt 2n2^n mögliche Zustände im worst-case, wobei nn die Anzahl der Zustände von MM ist.

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

Exercise 2: DFA-Algorithmen


Subproblem a (1.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, a -> q3
    q2, b -> q5
    q3, a -> q6
    q3, b -> q4
    q7, a -> q7
    q7, b -> q7
    q5, a -> q7
    q5, b -> q5
    q6, a -> q3
    q6, b -> q7
    q4, a -> q4
    q4, b -> q4
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 3
    q4: \emptyset
    q5: 0, 1, 2, 3
    q6: 1, 2
    q7: 1, 2, 3
7 wrong transitions (-4P)
wrong state sets for [3, 5] (-1P)

Subproblem b (0.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
Nein, da es äquivalente Zustände gibt. Beispielsweise sind q2 und q6 äquivalent, da sie für alle Eingaben in dieselben Zustandsklassen übergehen (z.B. führt 'a' beide nach q3 und 'b' nach {q5,q7}). Ebenso können q5 und q7 zusammengefasst werden, da sie identisches Akzeptanzverhalten zeigen.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0, 0), (1, 2), (2, 1), (2, 2), (2, 0)
Startzustand: (0, 0)
Finalzustände: (1, 2), (2, 1), (2, 2)
Transitionen:
(0, 0), a -> (1, 2)
(0, 0), b -> (0, 0)
(1, 2), a -> (2, 1)
(1, 2), b -> (2, 2)
(2, 1), a -> (2, 2)
(2, 1), b -> (2, 0)
(2, 2), a -> (2, 1)
(2, 2), b -> (2, 2)
(2, 0), a -> (2, 2)
(2, 0), b -> (2, 0)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:
Um MM' zu berechnen, führen wir eine modifizierte Potenzmengenkonstruktion durch. Zuerst berechnen wir für jeden Zustand qq von MM die Menge reachc(q)\text{reach}_c(q), bestehend aus allen Zuständen, die von qq aus durch beliebig viele cc-Übergänge erreichbar sind. Da MM ein DFA ist, bilden die cc-Übergänge deterministische Pfade, möglicherweise mit einer Schleife.

Der DFA MM' wird wie folgt konstruiert:
- Zustände: Alle Teilmengen der Zustände von MM, also P(Q)\mathcal{P}(Q).
- Startzustand: reachc(q0)\text{reach}_c(q_0), wobei q0q_0 der Startzustand von MM ist.
- Übergänge: Für eine Teilmenge SQS \subseteq Q und σ{a,b}\sigma \in \{a,b\} ist δ(S,σ)=qSreachc(δ(q,σ))\delta'(S, \sigma) = \bigcup_{q \in S} \text{reach}_c(\delta(q, \sigma)).
- Finalzustände: Alle Teilmengen SS, die mindestens einen Finalzustand von MM enthalten.

Die Anzahl der Zustände in MM' ist durch 2n2^n beschränkt, da es maximal 2n2^n Teilmengen der nn Zustände von MM gibt. Dies ist im Worst Case auch notwendig, z.B. wenn alle cc-Übergänge Selbstschleifen sind (reachc(q)={q}\text{reach}_c(q) = \{q\}), sodass die Konstruktion äquivalent zur Umkehrung des DFA ist, die bekanntermaßen 2n2^n Zustände benötigen kann.

x-ai/grok-4

Exercise 2: DFA-Algorithmen


Subproblem a (6.0/6.0P)

Wir betrachten den folgenden NFA NN über dem Alphabet Σ={a,b}\Sigma=\{a,b\}:
Zustände: 0, 1, 2, 3
Startzustand: 0
Finalzustände: 0, 2, 3
Transitionen:
    0, b -> 0
    0, b -> 1
    1, b -> 1
    1, b -> 2
    2, a -> 3
    2, b -> 3
    3, a -> 1
    3, a -> 2
Sei MM der DFA, den man erhält, wenn man NN mithilfe des Verfahrens aus der Vorlesung (Potenzmengenkonstruktion) zu einem DFA konvertiert. Tragen Sie MM in untere Schablone ein, indem Sie (1) die Transitionen beschriften, (2) die Finalzustände markieren, und (3) in der Tabelle rechts für jeden Zustand von MM die korrespondierende Menge an Zuständen aus NN eintragen.
Zustände: q0, q1, q2, q3, q4, q5, q6, q7
Startzustand: q0
Finalzustände: ?
Transitionen:
    q0 -> q1
    q0 -> q4
    q1 -> q2
    q1 -> q4
    q2 -> q3
    q2 -> q5
    q3 -> q3
    q3 -> q7
    q7 -> q7
    q7 -> q7
    q5 -> q4
    q5 -> q6
    q6 -> q5
    q6 -> q7
    q4 -> q4
    q4 -> q4
Zustandstabelle:
    q0:
    q1:
    q2:
    q3:
    q4:
    q5:
    q6:
    q7:
Finalzustände: q0, q1, q2, q3, q5, q6, q7
Transitionen:
    q0, b -> q1
    q0, a -> q4
    q1, b -> q2
    q1, a -> q4
    q2, b -> q3
    q2, a -> q5
    q3, b -> q3
    q3, a -> q7
    q7, a -> q7
    q7, b -> q7
    q5, b -> q4
    q5, a -> q6
    q6, a -> q5
    q6, b -> q7
    q4, a -> q4
    q4, b -> q4
Zustandstabelle:
    q0: 0
    q1: 0, 1
    q2: 0, 1, 2
    q3: 0, 1, 2, 3
    q4: \emptyset
    q5: 3
    q6: 1, 2
    q7: 1, 2, 3

Subproblem b (1.0/1.0P)

Ist M minimal? Begründen Sie Ihre Antwort kurz.
JaNein
Nein, da die Zustände q2 und q6 sowie q3 und q7 äquivalent sind. Daher hat der minimale DFA nur 6 Zustände und M ist nicht minimal.

Subproblem c (4.0/4.0P)

Im Folgenden sind zwei DFAs M1M_1 und M2M_2 angegeben. Berechnen Sie nach dem Algorithmus aus der Vorlesung (Produktkonstruktion) einen DFA MM mit L(M)=L(M1)L(M2)L(M)=L(M_1)\cap L(M_2) und tragen Sie das Ergebnis unten ein. Konstruieren Sie nur die erreichbaren Zustände.
M_1:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 1
    0, b -> 0
    1, a -> 2
    1, b -> 2
    2, a -> 2
    2, b -> 2
M_2:
Zustände: 0, 1, 2
Startzustand: 0
Finalzustände: 1, 2
Transitionen:
    0, a -> 2
    0, b -> 0
    1, a -> 2
    1, b -> 0
    2, a -> 1
    2, b -> 2
Zustände: (0,0), (1,2), (2,0), (2,1), (2,2)
Startzustand: (0,0)
Finalzustände: (1,2), (2,1), (2,2)
Transitionen:
(0,0), a -> (1,2)
(0,0), b -> (0,0)
(1,2), a -> (2,1)
(1,2), b -> (2,2)
(2,0), a -> (2,2)
(2,0), b -> (2,0)
(2,1), a -> (2,2)
(2,1), b -> (2,0)
(2,2), a -> (2,1)
(2,2), b -> (2,2)

Subproblem d (2.0/2.0P)

Geben Sie jeweils ein kürzestes Wort in L(M1)L(M2)L(M_1)\cap L(M_2), L(M1)L(M2)L(M_1)\setminus L(M_2) und L(M2)L(M1)L(M_2)\setminus L(M_1) an, oder \emptyset, falls kein solches Wort existiert.

Hinweis: Verwenden Sie Ihr Ergebnis aus c).
L(M1)L(M2)L(M_1)\cap L(M_2): aa
L(M1)L(M2)L(M_1)\setminus L(M_2): aabaab
L(M2)L(M1)L(M_2)\setminus L(M_1): \emptyset

Subproblem e (5.0/5.0P)

Sei L{a,b,c}L\subseteq\{a,b,c\}^* eine Sprache. Wir definieren die Sprache Rc(L){a,b}R_{c}(L)\subseteq\{a,b\}^* als die Menge der Wörter, die man erhält, wenn man aus jedem Wort von LL jedes Zeichen cc löscht.
Zum Beispiel gilt Rc({ba,bca,cc,ca})={ba,ε,a}R_{c}(\{ba, bca, cc, ca\})=\{ba,\varepsilon,a\}.

Sei MM ein DFA mit nn Zuständen. Wählen Sie eine Funktion f:NNf:\N\rightarrow\N, sodass es einen DFA MM' für Rc(L(M))R_{c}(L(M)) mit höchstens f(n)f(n) Zuständen gibt und beschreiben Sie einen Algorithmus, um MM' zu berechnen uns argumentieren Sie, wieso MM' höchstens f(n)f(n) Zustände hat.
Ihre Wahl: f(n):=2nf(n):=2^n
Begründung:
Konstruiere einen \epsilon-NFA NN wie folgt:
- Zustände: dieselben wie in MM (nn Zustände).
- Startzustand: Startzustand von MM.
- Finalzustände: Finalzustände von MM.
- Transitionen:
  - Für jedes qq und σ{a,b}\sigma \in \{a,b\}: qσδ(q,σ)q \xrightarrow{\sigma} \delta(q,\sigma) (wie in MM).
  - Für jedes qq: qϵδ(q,c)q \xrightarrow{\epsilon} \delta(q,c) (\epsilon-Transitionen simulieren cc-Übergänge).

Wende die Standardkonstruktion zur Beseitigung von \epsilon-Transitionen und Determinierung an (Potenzmengenkonstruktion mit \epsilon-Abschlüssen). Das resultierende DFA MM' hat höchstens 2n2^n Zustände, da es höchstens 2n2^n Teilmengen der nn Zustände gibt.

MM' erkennt Rc(L(M))R_c(L(M)), da eine akzeptierende Lauf von NN auf einem Wort w{a,b}w \in \{a,b\}^* einer Lauf von MM auf einem Wort uu entspricht, das durch Einfügen von cc's in ww entsteht (die \epsilon-Moves simulieren die cc's ohne Eingabe zu verbrauchen).