FSK-ÜB-2

Info

Wenn Sie Automaten angeben, tun Sie dies immer in Form eines Zustandsgraphen. Andere Formen der Darstellung (z.B. als Liste von Übergängen) werden nicht gewertet, da sie sehr viel aufwändiger zu korrigieren sind. Vergessen Sie nicht, im Zustandsgraph Start- und Endzustände zu markieren.

FSK2-1 Grammatik und Elimination von ε-Produktionen (2 Punkte)

a) Geben Sie kontextfreie Grammatiken (ggf. mit ε-Produktionen) an, die folgende Sprachen über dem Alphabet Σ = {a, b} erkennen:

i) $L_1=\{caw|c\in {\Sigma }^{\ast },w\in {\Sigma }^{\ast }\}$

• Alphabet: $\Sigma =\{a,b\}$
• 4-Tupel Grammatikform $G=(N,\Sigma ,P,S)$
• $N:\{S,C,B\}$ $$\begin{array}{rl}P:\{& \\ S& \to CaB\\ C& \to aA|bA|\epsilon \\ B& \to aB|bB|\epsilon \\ \}& \end{array}$$
• $S:S$ $$G=\{S,\{a,b\},\{S\to CaB,C\to aA|bA|\epsilon ,B\to aB|bB|\epsilon \},S\}$$

i) $L_2=\{aawbb|w\in {\Sigma }^{\ast }\}$

• Alphabet: $\Sigma =\{a,b\}$
• 4-Tupel Grammatikform $G=(N,\Sigma ,P,S)$
• $N:\{S,W,B\}$
• $S:S$

Erste Idee

$$\begin{array}{rl}P:\{& \\ S& \to aaW\\ W& \to aW|bW|B|\epsilon \\ B& \to bb\\ \}& \end{array}$$ $$G=\{S,\{a,b\},\{S\to aaW,W\to aW|bW|B|\epsilon ,B\to bb\},S\}$$

Zweite Idee (Besser?)

$$\begin{array}{rl}P:\{& \\ S& \to aaWbb\\ W& \to aW|bW|\epsilon \\ \}& \end{array}$$ $$G=\{S,\{a,b\},\{S\to aaWbb,W\to aW|bW|\epsilon \},S\}$$

b) Betrachten Sie die Grammatik $G=(\{A,B,C\},\{a,b\},P,A)$ mit Produktionen

Aufgabenstellung

$$P=\{A\to aBbC,A\to AaA,B\to \epsilon ,B\to CC,C\to BB\}$$

Geben Sie eine zu $G$ äquivalente Grammatik $G^{\prime }$ ohne ε-Produktionen an. Verwenden Sie den Algorithmus zur Elimination von ε-Produktionen aus der Vorlesung und geben Sie die Zwischenschritte Ihrer Berechnung an. (Das ermöglicht uns, Ihnen bei kleinen Fehlern noch Teilpunkte zu geben.)

Ziel: $\epsilon$ eliminieren

1. Schritt (ausfindig machen was $\epsilon$ bildet)

$$M=\{B,C\}$$

2. Schritt ($\epsilon$-freie Grammatik bilden — $\epsilon$ entfernen)

$$P=\{A\to aBbC,A\to AaA,B\to CC,C\to BB\}$$

3. Schritt ($\epsilon$-kompensieren)

$$\begin{array}{rl}P=\{A& \to aBbC|AaA|abC|aBb,\\ B& \to CC|C,\\ C& \to BB|B\}\end{array}$$

→ $A\to ab$ fehlt muss noch hinzugefügt werden

FSK2-2 DFAs und Minimierung (2 Punkte)

a) Geben Sie DFAs an, die folgende Sprachen über dem Alphabet Σ = {a, b} erkennen:

i) $L_1=\{caw|c\in {\Sigma }^{\ast },w\in {\Sigma }^{\ast }\}$

flowchart LR
	id1(( )) --> id2((z0))
	id2((z0)) --a,b--> id3((z1))
	id3((z1)) --a--> id5(((z2)))
	id3((z1)) --a,b--> id2((z0))
	id5(((z2))) --a,b--> id6(((z3)))
	id6(((z3))) --a,b--> id5(((z2)))

Falsch siehe Lösung

Erklärung des Gedankenganges, warum so dargestellt:

• Pfade zwischen $z_0$ und $z_1$ stellen $c$ dar, was eine Kette von Buchstaben vor $a$ ist
• Der Pfad von $z_1$ zu $z_2$ stellt $a$ dar, was immer steht
• $z_2$ ist ein akzeptierender Zustand, da $w\in {\Sigma }^{\ast }$ und auf das $a$ das leere Wort $\epsilon$ folgen kann
• Es kann aber auch eine Zeichenkette nach $a$ kommen, was mit den Pfaden zwischen $z_2$ und $z_3$ dargestellt wird
• $z_3$ ist ein Endzustand, für alle ungerade Anzahlen von Buchstaben nach $a$

ii) $L_2=\{aawbb|w\in {\Sigma }^{\ast }\}$

flowchart LR
	id0(( )) --> id1((z0))
	id1((z0)) --a--> id2((z1))
	id2((z1)) --a--> id3((z2))
	id3((z2)) --a--> id4((z3))
	id4((z3)) --a,b--> id3((z2))
	id3((z2)) --b-->id5((z4))
	id5((z4)) --a,b--> id3((z2))
	id4((z3)) --b--> id6((z5))
	id5((z4)) --b--> id6((z5))
	id6((z5)) --b--> id7(((z6)))

$z_0$ und $z_1$ landen im Müllzustand

Erklärung des Gedankenganges, warum so dargestellt:

• Pfade von $z_0$ bis $z_2$ stellt $aa$ im Wort da
• Pfade zwischen $z_2,z_3$ und $z_4$ stellen das Wort $w$ dar
• Die $b$ Pfade ab $z_3$ und $z_4$ bis $z_6$ stellen das $bb$ nach dem $w$ dar
• $z_6$ ist ein akzeptierender Zustand, da das Wort ab da immer garantiert mit $bb$

b) Minimieren Sie die folgenden DFAs. Verwenden Sie die tabellarische Variante des Algorithmus zur Minimierung von DFAs aus der Vorlesung (nicht die grafische Variante und nicht den Algorithmus von letztem Jahr!). Geben Sie die Partitionstabelle und den minimalen DFA an.

i) DFA A1 über dem Alphabet $\Sigma =\{a\}$:

graph LR
	id1(( )) --> circleId0(("`z0`"))
    circleId0(("`z0`")) -->|a| circleId1(("`z1`"))

    circleId1(("`z1`")) -->|a| circleId2(("`z2`"))

    circleId2(("`z2`")) -->|a| doubleCircleId3((("`z3`")))

    doubleCircleId3((("`z3`"))) -->|a| circleId4(("`z4`"))

    circleId4(("`z4`")) -->|a| circleId5(("`z5`"))

    circleId5(("`z5`")) -->|a| circleId6(("`z6`"))

    circleId6(("`z6`")) -->|a| doubleCircleId7((("`z7`")))

    doubleCircleId7((("`z7`"))) -->|a| circleId0(("`z0`"))

• Endzustände $z_3$ und $z_7$ werden getrennt

$$z_0{z}_1{z}_2{z}_4{z}_5{z}_6|z_3{z}_7$$

• $z_2$ und $z_6$ führen in Klasse 2 bzw. in andere Partition, deswegen teilen wird diese

$$z_0{z}_1{z}_4{z}_5|z_2{z}_6|z_3{z}_7$$

• Jetzt führen aber $z_1$ und $z_5$ auch in andere Partitionen und müssen geteilt werden

$$z_0{z}_4|z_1{z}_5|z_2{z}_6|z_3{z}_7$$

---
title: Graphische Darstellung der Partitionen
---
graph LR
    id1(( )) --> circleId0(("`P0`"))
    circleId0(("`P0`")) -->|a| circleId1(("`P1`"))
    circleId1(("`P1`")) -->|a| circleId2(("`P2`"))
    circleId2(("`P2`")) -->|a| doubleCircleId3((("`P3`")))
    doubleCircleId3((("`P3`"))) -->|a| circleId0(("`P0`"))

ii) DFA A2 aber dem Alphabet $\Sigma =+,-,.,0,\dots ,9$ (bekannt aus der Vorlesung)

Graph aus Blatt entnehmen

$z10$ Müllzustand fehlt muss als nicht Endzustand behandelt werden $z_4$ und $z_8$ müssen noch partitioniert werden, da sie in eine andere Partition führen, da jeweil 2 Pfeile von diesen Zuständen ausgehen, einmal auf sich selbst und einmal auf einen anderen Zustand

$$z_0{z}_1{z}_2{z}_3{z}_4{z}_5{z}_6{z}_7{z}_8{z}_9$$

• Endzustände $z_3,z_4,z_5,z_7,z_8,z_9$

$$z_0{z}_1{z}_2{z}_6|z_3{z}_4{z}_5{z}_7{z}_8{z}_9$$

• $z_6$ und $z_2$ führen in andere Partition werden deswegen getrennt

$$z_0{z}_1|z_2{z}_6|z_3{z}_4{z}_5{z}_7{z}_8{z}_9$$

• $z_1$ führt in 2 andere Partition deswegen trennen

$$z_0|z_1|z_2{z}_6|z_3{z}_4{z}_5{z}_7{z}_8{z}_9$$

FSK2-3 Kleine Automaten (0 Punkte)

a) Sei $A_1$ ein DFA mit Alphabet $\Sigma$ und genau einem Zustand. Zeigen oder widerlegen Sie: Es ist entweder $L(A_1)={\Sigma }^{\ast }$ oder $L(A_1)=\varnothing$.

Gedankengang:

• Wenn das DFA nur einen Zustand hat, kann dieser entweder akzeptieren sein oder nicht

Beweis:

• Es gibt 2 Fälle für $A_1$:
  • Der Zustand von $A_1$ ist ein akzeptierender Zustand
  • Der Zustand von $A_1$ ist kein akzeptierender Zustand
• Der Zustand von $A_1$ sei deklariert als $z_0$
• Alle Pfade von $z_0$ führen zurück zu $z_0$
• Erster Fall: akzeptierender Zustand

graph LR
id0(( )) --> id1(((z0))) --w∈Σ--> id1(((z0)))

• Da $z_0$ der akzeptierende Zustand ist, kann man damit alle Wörter aus $\Sigma$ darstellen

  • Beim Lesen von jedem String landet der Automat in $z_0$ was ein akzeptierender Zustand ist
  • Es gilt also: $L(A_1)={\Sigma }^{\ast }$

• Zweiter Fall: nicht akzeptierender Zustand

graph LR
id0(( )) --> id1((z0)) --w∈Σ--> id1((z0))

• Da $z_0$ kein akzeptierender Zustand ist, landet der Automat beim lesen in keinen akzeptierenden Zustand, was dazu führt, dass kein Wort gültig ist
  • Es gilt also: $L(A_1)=\varnothing$
  $$\text{\hspace{1em}■}$$ Schlussfolgerung: Die Behauptung ist wahr. Für einen DFA $A1$ mit genau einem Zustand ist die von ihm akzeptierte Sprache entweder ${\Sigma }^{\ast }$ oder $\varnothing$, abhängig davon, ob der einzige Zustand ein akzeptierender Zustand ist oder nicht.

b) Sei $A_2$ ein DFA mit Alphabet $\Sigma =\{a,b\}$ und genau zwei Zuständen. Angenommen es gibt ein Wort $z\notin L(A_2)$ und für alle $i\in \mathbb{N}$ ist $a^i\in L(A_2)$. Zeigen oder widerlegen Sie: Für jeden solchen Automaten $A_2$ ist $bb\notin L(A_2)$.

Widerleg durch Gegenbeispiel

graph LR
id0(( )) --> id1((z1))
id1((z1)) --a,b--> id2(((z2)))
id2((z2)) --a,b--> id2(((z2)))

Dieser Automat kann das Wort $bb$ Produzieren und besteht aus genau zwei Zuständen. Also gilt $bb\in L(A_2)$

c) Zeigen Sie: Für jeden DFA mit Alphabet $\Sigma =\{a,b\}$ und genau vier Zuständen gilt: Wenn für jede natürliche Zahl $n\ge 1$ das Wort $a^{n^2}$ in $L(A)$ ist, dann ist auch $a^{12}\in L(A)$.

Erster Ansatz Induktion

Beweis durch Induktion: Induktionsanfang: Es wird bewiesen, dass die Aussage für die kleinste Zahl, den Startwert, gilt.

$$\begin{array}{r}n=1:a^{1^2}=a^1\end{array}$$

Indutktionsannahme: Gilt die Aussage für eine beliebige Zahl, so gilt sie auch für deren Nachfolge

$$n\to n+1$$

Induktionsschritt:

$$\begin{array}{rl}{a}^{(n+1{)}^2}& =a^{n^2+2n+1}\\ & =a^{n^2}\cdot a^{2n+1}\end{array}$$

Da nach der Induktionsannahme $a^{n^2}$ wahr ist, und weil $a^{2n+1}$ eine korrekte Anwendung der Potenzgesetze ist, ist auch $a^{(n+1{)}^2}$ wahr.

Zusammenfassung: Durch den Induktionsanfang und den Induktionsschritt haben wir gezeigt, dass $a^{k^2}$ für alle natürlichen Zahlen $k$ gilt, beginnend bei $k=1$. Somit gilt die Aussage auch für $a^{12}$

FSK2-4 Grammatik-Konkatenation (0 Punkte)

• FSK 2-4 verstehen was abgeht [completion:: 2024-07-15]

Aufgabenstellung

Seien $G$ und $G^{\prime }$ Typ-i-Grammatiken (für $i\in \{0,\dots ,3\}$), sodass $\epsilon \notin L(G)$ und $\epsilon \notin L(G^{\prime })$. Zeigen oder widerlegen Sie für alle $i$: Es gibt eine Grammatik $G^{\prime \prime }$ vom Typ $i$, sodass $L(G^{\prime \prime })=L(G)L(G^{\prime })$.

Die Aufgabenstellung erfordert den Nachweis, dass für jede Typ-i-Grammatik (wobei $i\in \{0,1,2,3\}$) $G$ und $G^{\prime }$, die $\epsilon$ nicht enthalten, eine entsprechende Grammatik $G^{\prime \prime }$ existiert, deren Sprache der Konkatenation der Sprachen von $G$ und $G^{\prime }$ entspricht, also $L(G^{\prime \prime })=L(G)L(G^{\prime })$.

Typ-0 (Rekursiv aufzählbare Grammatiken):

• Typ-0-Grammatiken können jede berechenbare Sprache generieren, einschließlich der Konkatenation zweier Sprachen. Dies wird erreicht, indem die Produktionen von $G$ mit denen von $G^{\prime }$ kombiniert werden, wobei das Ende der Produktionen von $G$ direkt zum Beginn der Produktionen von $G^{\prime }$ übergeht.

Typ-1 (Kontextsensitive Grammatiken):

• Für Typ-1-Grammatiken kann eine Grammatik $G^{\prime \prime }$ konstruiert werden, die zuerst ein Wort aus $L(G)$ und dann aus $L(G^{\prime })$ erzeugt, ohne die Kontextsensitivität zu verletzen.

Typ-2 (Kontextfreie Grammatiken):

• Die Konstruktion von $G^{\prime \prime }$ für kontextfreie Grammatiken umfasst die Einführung eines neuen Startsymbols und Regeln, die zuerst ein Wort aus $L(G)$ und anschließend aus $L(G^{\prime })$ generieren.

Typ-3 (Reguläre Grammatiken):

• Reguläre Grammatiken unterstützen die Konkatenation, indem das Endsymbol der Regeln von $G$, das sonst auf das leere Wort führt, durch das Startsymbol von $G^{\prime }$ ersetzt wird.

Zusammengefasst ist es für alle Grammatiktypen möglich, die Konkatenation ihrer Sprachen durch eine Grammatik des gleichen Typs zu realisieren.

---

$$L\subseteq {\Sigma }^{\ast }\text{ heisst }\underline{erkennbar},falls\exists \mathcal{A}mitL(\mathcal{A})=L$$

---

---