# FSuB blatt 6
## Aufgabe 21

Wir wollen einen Kellerautomaten konstruieren, der die Sprache
$L = \{w ∈ Σ^{*} | \ |w|_b = |w|_c\} \ mit \ Σ = \{a, b, c\}$ akzeptiert.

Um die Anzahl der b’s kontrollieren zu können, legen wir alle gelesenen b´s in den Keller ab. Beim Lesen der C’s streichen wir eine obersten Kellersymbol aus dem Keller. Beim lesen a’s strichen wir eine obersten Kellersymbol aus dem Keller und das Eingabewort abgearbeitet, dann wird das Eingabewort akzeptiert. Der Kellerautomat

K = ({ a, b, c }, { s0, s1, sf }, { A, B, ⊥ }, δ, s0, ⊥, {$s_f$ })
Mit

δ = { ($s_0$, a, ⊥, $s_0$,B⊥), (1.1)
($s_0$, b, A, $s_0$, B), (1.2)

($s_0$, b, B, $s_1$, B), (1.3)

($s_0$, c, B, $s_1$, ε), (1.4)

($s_0$, c, B,$s_f$, ε),(1.5)

($s_1$, b, B, $s_1$, B), (1.6)

($s_1$, c, B, $s_1$, ε), (1.7)

($s_1$, a, B, $s_f$, ε), (1.7)

($s_1$, ε, ⊥, $s_f$, ε) } (1.9)

akzeptiert L mit Endzustand.

**korrekeit:**
Der Übergang (1.1) legt das erste B auf den Keller, (1.2), (1.3), und (1.6) legt alle weiteren B’s auf den Keller. In (1.4), (1.5) wird das erste c gelesen und das oberste B gelöscht. In (1.7) werden alle folgenden c’s gelesen und für jedes c ein B gelöscht. In (1.8) wird das a gelesen und das oberste B gelöscht. In (1.9) geht der Automat, falls das Eingabewort abgearbeitet ist und der Keller leer ist (⊥ ist erreicht), in den Endzustand. Falls mehr c’s als b’s im Eingabewort sind, wird das Eingabewort nicht abgearbeitet, und damit das Eingabewort nicht akzeptiert. Falls mehr c’s als b’s im Eingabewort sind, da s1 für eine für eine kellersymbole A nicht definiert ist. d.h. das Eingabewort wird nicht weiter abgearbeitet. Man kann zeigen, dass L = $L_F$ (K) gilt.

**Beispiel**

Wir wollen für das Wort abbcc die Folge der Konfigurationsübergänge bestimmen:
($s_0$, abbcc, ⊥) $\Rightarrow$ ($s_0$, bbcc, A⊥) $\Rightarrow$ ($s_0$, bcc, BA⊥) $\Rightarrow$ ($s_1$, cc, BBA⊥) $\Rightarrow$ ($s_1$, c, BA⊥) $\Rightarrow$ ($s_1$, ε, A⊥) $\Rightarrow$ ($s_f$, ε, ε)

Es gilt also ($s_0$, abbcc, ⊥) $\Rightarrow$ ($s_f$ , ε, ε) und damit ist abbcc ∈ $L_F$ (K), da sf Endzustand ist.

## Aufgabe 21
* Die folgende Grammatik $G$ erzeugt genau die Sprache $L$:
\begin{equation}
G=\{V=\{Z,S\},\Sigma=\{a,b,c\},P,Z\}
\end{equation}
wobei
\begin{align}
P=\{
Z &\to \epsilon|S&(R1)\\
S &\to aS|Sa|a&(R2)\\
S &\to SS|bSc|cSb|bc|cb\}&(R3)\\
\end{align}
Begründung:
* $L\subseteq L(G)$: $L(G)$ enthält alle Wörter $w$ in $L$
1. Fall: $w$ hat kein $b$ und $c$, also $|w|_b=|w|_c=0$: $w$ ist das leere Wort oder besteht aus beliebigen vielen $a$'s und keinem $b$ oder $c$ $\Rightarrow w$ lässt sich durch $R1, R2$ ableiten. $R1$ erzeugt das leere Worte und $R2$ kann beliebig viel angewendet werden, um die gewünschte Anzahl von $a$'s zu erreichen.
2. Fall: $w$ hat so viel $b$'s wie $c$'s, also $|w|_b=|w|_c=n, n\in N$: $w$ hat die gleiche Anzahl von $b$'s und $c$'s, darf aber beliebig viele $a$'s enthalten. Wir machen hier eine weitere Fallunterscheidung:
* a) Wenn das Wort $w$ mit entweder $b$ oder $c$ endet und anfängt: Wir wenden zunächst $R1$ an, um $S$ aus Startvariable Z abzuleiten. Nach $R3$ ersetzen wir nun diese $S$ mit einer Satzform von $b$ und $c$. Falls zwischen den $b$'s und $c$'s noch $i$-mal $a$'s zu ergänzen sind, wird ein $S$ zwischen $b$ und $c$ durch $aS|Sa$ oder direkt durch $a$ (wenn $i$=1) ersetzt $(R2)$. Mit $S\to aS|Sa$ erhalten wir ein $a$ und eine extra Variable $S$, mit welcher wir sowohl so viel weitere $a$'s wie gewünscht bilden als auch weitere $b$'s und $c$' ableiten können. Wiederholen den Prozess bis zum alle $n$-Paare von $b$'s und $c$'s abgeleitet ($n$ Ableitungen nach $R3$) und alle benötigten $a$'s zwischen diesen $b$'s und $c$'s eingefügt ($i$ Ableitungen nach $R2$) werden; also bis zum wir das Wort $w$ erhalten.
* b) Endet das Wort mit $m$-mal $a$'s, wenden wir zunächst $R1$ an um $S$ aus $Z$ abzuleiten. Nach $R2$ ersetzen wir diese Variable $S$ durch $Sa$. Diese Regel wenden wir $m$-mal an, nun sind alle $a$'s am Ende $w$abgeleitet, es bleibt nur noch eine Variable $S$ am Anfang, diese behandeln wir wie in a).

* c) Fängt das Wort mit $m$-mal $a$'s an, leiten wir $S$ aus $Z$ nach $R1$ ab. Wir wenden $m$-mal $S\to aS$ auf $S$ an, erhalten damit alle $a$ am Anfang von $w$. Die verbleibende $S$ am Ende der Satzform behandeln wir wie in a)

* d) Fängt das Wort mit $j$-mal $a$'s an und endet es mit $k$-mal $a$'s: Nach dem wir $S$ aus $Z$ abgeleitet haben, wenden wir $j$-mal $S\to aS$ an. Damit ist die Ableitung der ersten j $a$'s erledigt. Die verbleibende $S$ Variable ersetzen wir durch $Sa$, und zwar $k$-mal so. Nun ist die Ableitung der letzten k$a$'s auch erledigt, es ist nur noch eine Variable $S$ im Mittel der Satzform geblieben. Diese $S$ behandeln wir wie oben in a)

$\forall x\in L, x$ ist entweder in der Wortgruppe von 1.Fall oder 2.Fall $\Rightarrow x$ lässt sich mit den Produktionregeln von $G$ erzeugen.
$\Rightarrow \forall x \in L, x \in L(G)$
$\Rightarrow L\subseteq L(G)$

* $L(G)\subseteq L$
Es ist ersichtlich, dass nur Wörter erzeugt werden können, die genauso viele $b$'s wie $c$'s und beliebig vielen $a$'s enthalten, da jede Regel die gleiche Anzahl von $b$'s und $c$'s erzeugt und $Z$ selbst als startende Satzform weder $b$'s noch $c$'s enthält. $G$ akzeptiert das leere Wort und erlaubt beliebig viel $a$'s in jedem Wort $w \in L(G)$. Damit gilt für jedes ableitbare Wort, dass es ein Element von $L$ ist.
$\Rightarrow L(G)\subseteq L$
* Nach dem Verfahren im Schöning (s.64-65) konstruieren wir den folgenden Automaten $M$:
\begin{equation}
M=\{\{z\},\Sigma=\{a,b,c\},V\cup \Sigma,\delta,z,Z\}
\end{equation}
wobei $\delta$ wie folgt definiert wird:

\begin{align}
\delta(z,\varepsilon,Z) &\ni (z,\varepsilon)\\
\delta(z,\varepsilon,Z) &\ni (z,S)\\
\delta(z,\varepsilon,S) &\ni (z,aS)\\
\delta(z,\varepsilon,S) &\ni (z,Sa)\\
\delta(z,\varepsilon,S) &\ni (z,a)\\
\delta(z,\varepsilon,S) &\ni (z,SS)\\
\delta(z,\varepsilon,S) &\ni (z,bSc)\\
\delta(z,\varepsilon,S) &\ni (z,cSb)\\
\delta(z,\varepsilon,S) &\ni (z,bc)\\
\delta(z,\varepsilon,S) &\ni (z,cb)\\
\delta(z,a,a) &\ni (z,\varepsilon)\\
\delta(z,b,b) &\ni (z,\varepsilon)\\
\delta(z,c,c) &\ni (z,\varepsilon)\\
\end{align}
* Es gilt nun für alle $x\in L$
$\Leftrightarrow x \in L(G)$
$\Leftrightarrow$ es gibt eine Ableitung in G der Form $Z \Rightarrow \dots \Rightarrow x$
$\Leftrightarrow$ $(z,x,Z)\vdash^{*} K$ und es existiert $z$ mit $(z,\varepsilon,\varepsilon)\in K$
$\Leftrightarrow x \in N(M)$
$\Leftrightarrow$ Der Automat $M$ akzeptiert die Sprache L.

## Aufgabe 22
* Nach dem Verfahren im Schöning (s.65) konstruieren wir die folgende Grammatik $G$:
\begin{equation}
G=\{V=\{S\}\cup Z\times\Gamma\times Z,\Sigma=\{a,b\},P,S\}
\end{equation}
wobei:
\begin{align}
P&=\{S\to(q_0,\#,q_0)|(q_0,\#,q_1)|(q_0,\#,q_2)\}&(R_S)\\
&\cup\{(q_1,B,q_2)\to b\} &(R_0)\\
&\cup\{(q_2,A,q_2)\to b\} &(R_1)\\
&\cup\{(q_0,\#,q_0)\to a(q_1,\#,q_0);&(R_2)\\
&(q_0,\#,q_1)\to a(q_1,\#,q_1);&(R_3)\\
&(q_0,\#,q_2)\to a(q_1,\#,q_2) \}&(R_4)\\
&\cup\{(q_1,\#,q_0)\to a(q_1,B,q_0)(q_0,A,q_0)&(R_5)\\
&(q_1,\#,q_0)\to a(q_1,B,q_1)(q_1,A,q_0)&(R_6)\\
&(q_1,\#,q_0)\to a(q_1,B,q_2)(q_2,A,q_0)&(R_7)\\
&(q_1,\#,q_1)\to a(q_1,B,q_0)(q_0,A,q_1)&(R_8)\\
&(q_1,\#,q_1)\to a(q_1,B,q_1)(q_1,A,q_1)&(R_9)\\
&(q_1,\#,q_1)\to a(q_1,B,q_2)(q_2,A,q_1)&(R_{10})\\
&(q_1,\#,q_2)\to a(q_1,B,q_0)(q_0,A,q_2)&(R_{11})\\
&(q_1,\#,q_2)\to a(q_1,B,q_1)(q_1,A,q_2)&(R_{12})\\
&(q_1,\#,q_2)\to a(q_1,B,q_2)(q_2,A,q_2)\}&(R_{13})
\end{align}
* Das Wort $aabb$ lässt sich wie folgt ableiten:
\begin{align}
S\Rightarrow^{R_S}(q_0,\#,q_2)\Rightarrow^{R_4}a(q_1,\#,q_2)\Rightarrow^{R_{13}}aa(q_1,B,q_2)(q_2,A,q_2)\Rightarrow^{R_0}aab(q_2,A,q_2)\Rightarrow^{R_1}aabb
\end{align}