Chomsky-Hierarchien

Reguläre Sprachen

Eigentlich beschreibt ein regulärer Ausdruck $\small E$ die reguläre Sprache $\small L(E)$ .

$\mathcal{L}_{\text {reg }}(\Sigma)$ ist die kleinste Menge für die gilt

$\small\{\},\{a \in \Sigma \} \color{grey}\in \mathcal{L}_{\text {reg }}(\Sigma)$

$\small A, B \textcolor{grey}{\in \mathcal{L}_{\mathrm{reg}}(\Sigma)} \implies A \cup B, ~~A \cdot B,~~ A^{*} \color{grey}\in \mathcal{L}_{\text {reg }}(\Sigma)$

Leerwort auch gültig da $\small \{\} ^* = \{\varepsilon\}$

Algebraische Notation

$*$ hat höchste Priorität, $+$ hat niedrigste Priorität

$\small s$ statt $\small \{s\}$ für $\small s \in (\Sigma \cup \varepsilon)$

$\small \empty$ statt $\small \{\}$

$\small L_1+L_2$ statt $\small L_{1} \cup L_{2}$

$\small L_{1} L_{2}$ statt $\small L_{1} \cdot L_{2}$

$\small L^{*}$ bleibt $\small L^{*}$

Abgeschlossenheit

$\small A, B \textcolor{grey}{ \in \mathcal{L}_{\mathrm{reg}}(\Sigma) }\implies$

$\small A \cup B, ~~A \cdot B,~~ A^{*} \color{grey} \in \mathcal{L}_{\text {reg }}(\Sigma)$

$\small A^+ = A^* \cdot A \color{grey}\in \mathcal{L}_{\text {reg }}(\Sigma)$

$\small A \cap B=\overline{\bar{A} \cup \bar{B}}\color{grey}\in \mathcal{L}_{\text {reg }}(\Sigma)$

$\small A-B=A \cap \bar{B} \color{grey}\in \mathcal{L}_{\text {reg }}(\Sigma)$

Komplement über $\small \Sigma^*$

DEA erzeugen wobei Endzustände und Nicht-Endzustände vertauscht wurden

Spiegelung

EA erzeugen, wobei Start und Endzustand vertauscht wurden

Homomorphismen

regulärer Ausdruck wo alle $\small a$ mit $\small h(a)$ ersetzt wurden

Homomorphismus

$\small h(L)=\{h(w) \mid w \in L\}$

$\small h: \Sigma \longmapsto \Gamma^{*}$

$\small h(\varepsilon)=\varepsilon$

$\small \forall w \in \Sigma^{*}, ~ a \in \Sigma:~ h(w a)=h(w) h(a)$

Reguläre Sprachen sind rekursive Probleme

$\small P=\{w \mid w \in L\}$ (Wortproblem)

Gehört $w$ der Sprache $\small L$ an?

Lösung: DEA für $\small L$ erzeugen und $\small \delta^{*}(q_{0}, w) \in F$ prüfen.

$\small P=\{w \mid w \in \{\}\}$

Ist $\small w$ leer?

Lösung: DEA für $\small L$ erzeugen und $\small \exists w: \delta^{*}\left(q_{0}, w\right) \in F$ prüfen.

Ist $\small L$ endlich oder unendlich?

Lösung: Minimale DEA für $\small L$ erzeugen. Falls sie abgesehen von Falle einen Zyklus enthält ist sie unendlich.

Ist $\small L=L'$ ?

Lösung: Überprüfen ob $\small L-L' = L-L' = \empty$

Endlicher Automat zur regulären Sprache

Zu jeder regulären Sprache $L$ gibt es einen endlichen Automaten $\mathcal A$ , sodass $L = L(\mathcal A)$ .

Minimalautomat

Reguläre Sprache $\mapsto$ eindeutiger DEA mit minimaler Anzahl an Zuständen

Kann mit dem Minimierungsalgorithmus von Brozozowski erhalten werden.

Pumping Lemma für reguläre Sprachen

Nicht-reguläre Sprachen

Wenn es keine DEA für $\small L$ gibt.

Wenn die Sprache unbeschränkten Speicher braucht.

zb wenn wir unbegrenzt viele Zustände brauchen um eine Anzahl zu merken.

$\small L=\left\{0^{n} 1^{n} \mid n \geq 0\right\}$

$\small A=\{w \mid w \text { enthält gleich viele } 0 \text { wie } 1\}$

Schubfachprinzip (Pigeonhole principle)

(Teil des Beweises dass Sprache nicht regulär ist)

$\small n+1$ Gegenstände auf $\small n$ Schubfächer $\Rarr$ in einem Schubfach müssten 2 Gegenstände sein.

DEA $\mathcal A$ hat $m$ Zustände, Wort aus $w$ Sprache hat mehr: $|w| \geq m$

Ein Zustand muss mehrfach durchlaufen werden.

Algorithmus:

Zerlege $w$ in $xyz$ (Abschnitt-1, Schleife, Abschnitt-2)

Alle wörter $x y^{i} z$ werden ebenfalls von $\mathcal A$ akzeptiert.

Pumping Lemma für reguläre Sprachen

In unendlichen regulären Sprachen $L$ enthält jedes Wort $w \in L$ ab einer bestimmten Länge $|w|\geq m$ einen Abschnitt, dass beliebig wiederholt werden kann und trotzdem von der Sprache akzeptiert wenn:

$w = xyz$

$|xy| \leq m$

$|y| > 0$

Dann gilt:

$\forall i \geq 0:~ w_i = xy^iz \in L$

Beispiel: Beweis dass Sprache nicht regulär ist

$L=\left\{a^{n} b^{n} \mid n \geq 0\right\}$

Beweis durch widerspruch:

Angenommen $L$ sei regulär.

Wir wählen irgendein beliebiges $m$ und $w \in L$ sodass $a^mb^m =w$

Daraus folgt $\small |w|\geq m$ da $\small |w| = 2\cdot m$

Wir wählen irgendeine beliebige Zerlegung $xyz = w$ unter den Bedingungen

$\small |xy| \leq m$ (für das $\small m$ dass vorher bestimmt wurde)

$\small |y| > 0$

$\small xy$ kann nur aus Symbol $\small a$ bestehen.

Wir wählen ein einziges beliebiges $i$

zB $\small i = 2$

Dann müsste wenn $L$ regulär wäre, auch $x y^{2} z=a^{m+|y|} b^{m} \in L$

Das ist nicht der Fall.

Kontextfreie Sprachen

Kontextfrei bedeutet dass die Ableitungs-Art keine Rolle spielt und man immer mit der kontextfreien Grammatik die selbe Sprache erzeugt.

Beispiele

Wohlgeformte Klammerausdrücke WKA

$G=\langle\{A\},\{(,)\},\{A \rightarrow \varepsilon|(A)| A A\}, A\rangle$

Palindrome über $\small \{a, b\}$

$\begin{aligned} G=&\lang S,\{a, b\}\\ &\{S \rightarrow \varepsilon|a| b|a S a| b S b\}, S\rangle \end{aligned}$

Wichtig:

$\{ww^r \mid w \in \{a,b\}^* \}$ ist nicht dasselbe wie

$\{w \in \{a,b\}^* \mid w = w^r\}$

(Entscheidungs-)Probleme die über kontextfreie Sprachen $L$ definiert werden:

Rekursiv

Ist $L$ leer / endlich / unendlich?

$w\in L$ ? (Wortproblem)

Nicht rekursiv

$L=\Sigma^*$ ?

$L_1=L_2$ ? (Äquivalenzproblem)

$L_{1} \subseteq L_{2}$ ?

$L_{1} \cap L_{2}=\{\}$ ?

Ist $L$ regulär?

Ist $L_{1} \cap L_{2}$ kontextfrei?

Ist $\Sigma^{*}-L$ kontextfrei?

Satz von Chomsky-Schützenberger

Dyck-Sprachen

Alphabet bestehend aus den Klammerpaaren $\small 1$ bis $\small n$ :

$\Gamma_{n}=\left\{(_1,)_{1}, \ldots,(_n,)_{n}\right\}$

$D_{n}$ über das Alphabet $\Gamma_{n}$ ist die kleinste Menge für die gilt:

$\varepsilon \in D_{n}$

$v \in D_{n} \implies \textcolor{pink}{(_{i}} v \textcolor{pink}{)_{i}} \in D_{n}, 1 \leq i \leq n$

$v_{1}, v_{2} \in D_{n} \implies v_{1}\cdot v_{2} \in D_{n}$

Satz von Chomsky-Schützenberger

Jede kontextfreie Sprache ist ein homomorphes Bild von dem Durschschnitt

von einer regulären Sprache mit einer Dyck-Sprache

Sprache $L$ ist kontextfrei wenn zu einem $n\geq 0$ es ein $h: \Gamma_{n}^{*} \longmapsto\Sigma^{*}$ gibt, sodass:

$L=h\left(D_{n} \cap R\right)$

Wobei $R$ eine reguläre Sprache und $D_n$ eine Dyck-Sprache über $\Gamma_n$ ist.

Beispiel

$L=\left\{a^{n} b^{n} \mid n \geq 0\right\}$ ist kontextfrei

$L=h\left(D_{1} \cap\left\{\textcolor{pink}(\}^{*}\{\textcolor{pink})\right\}^{*}\right)$

Wir haben als Definitionsmenge für die Homomorphismus-Funktion den Durchschnitt zwischen $D_1=\textcolor{pink}(\textcolor{pink})$ und $\{\textcolor{pink}(\}^{*}\{\textcolor{pink})\}^*$ .

Die Dyck-Sprache beinhaltet nicht nur nested brackets sondern auch die Konkatenation wie $\color{pink}()()$ .

Kontextfreie Sprachen über 1-Element-Alphabet

Jede kontexfreie Sprache über einem einelementigen Alphabet ist regulär.

Pumping Lemma für kontextfreie Sprachen

Lemma

Sei $L$ eine unendliche kontextfreie Sprache.

$\forall w \in L:$ wenn $|w| \geq m >0$ dann existiert eine Zerlegung

$w = uvxyz$

$|v x y| \leq m$

$|v y| \geq 1$

Und $\forall i \geq 0:$

$w_{i}=u v^{i} x y^{i} z \in L$

Beweis

Wir wollen beweisen, dass das obige Lemma für kontextfreie Sprachen gilt.

Bei regulären Sprachen argumentiert man mit Zuständen in Pfaden von DEA, hier mit Anzahl der Nonterminale in Pfaden von binären Ableitungsbäumen (in der Chomsky NF).

Sei $G$ eine kontextfreie Grammatik in Chomsky NF.

Der längste Pfad im Ableitungsbaum von $G$ hat $k$ Nonterminale .

Wähle beliebiges $w \in L(G)$ mit $|w| \geq 2^k = m$

Die Konkatenation von allen Terminalen, die an der Front erreicht wurden ist das abgeleitete Wort

Daraus folgt:

Baum muss $\geq 2^k$ Leafs haben.

Die leafs bestimmen die depth von $\log_2(2^k) = k$ .

Es muss einen Pfad der Länge $\geq k+1$ (inklusive Startsymbol) geben.

Es müssen sich am Pfad $\geq k+1$ Nonterminale befinden (obwohl wir nur $k$ Nonterminale haben.)

Ein Nonterminal muss mindestens doppelt vorkommen.

Es werden Abschnitte im Baum wiederverwendet.

Wir betrachten die Teilwörter für die, die Node / das Nonterminal $A$ mehrfach im Pfad vorkommt.

Wir wählen 2 sich wiederholende Abschnitte.

$w = u\underbrace{v\underbrace{x}_{1}y}_{2}z$

Da das obere $A$ , zuständig für Abschnitt 2 nicht leer sein kann, dürfen $v, y$ nicht leer sein.

Alternative Möglichkeiten
$u x z=u v^{0} x y^{0} z \in L(G)$
$u v v x y y z=u v^{2} x y^{2} z \in L(G)$

Allgemein gilt für jeden Baum

$\forall i \geq 0: u v^{i} x y^{i} z \in L(G)$

Folgerung: Pumping Lemma Kollorar

Für alle Sprachen

$L \subseteq\{a\}^{*}$

$L=\left\{a^{f(n)} \mid n \geq 0\right\}$

mit streng monoton wachsender Funktion $f$ in $\N$ und bijektiver Abbildung $n(k)$ für jedes $k$ sodass

$f(n(k+1))-f(n(k)) \geq k$

gilt, $L$ ist nicht kontextfrei.

Beispiele
$\left\{a^{p} \mid p \text { ist eine Primzahl }\right\}$
$\left\{a^{2^{n}} \mid n \geq 0\right\}$

Pumping Lemma - Beispiel

$L=\left\{a^{n} b^{n} c^{n} \mid n \geq 0\right\}$ ist nicht kontextfrei.

Beweis

Angenommen $L$ wäre kontextfrei, wählen wir $m$ :

$w = a^mb^mc^m$

$\forall w\in L: |w|_{a}=|w|_{b}=|w|_{c}$

$|w|=3 m>m$

Wir zerlegen $w$ in:

$w=u v x y z$

$u$ muss immer das Symbol $a$ enthalten, $z$ immer das Symbol $c$

$|v x y| \leq m$

Wir stellen uns diesen Abschnitt wie einen Rahmen vor, den wir über Teilwörter von $w$ schieben können.

$|v y| \geq 1$

Daraus folgt, dass $vxy$ nicht gleichzeitig alle 3 Symbole $a,b,c$ umfassen kann.

Entweder $|v x y|_{a}=0$ oder $|v x y|_{c}=0$ weil sie zu weit auseinander liegen.

Wir untersuchen alle möglichen Fälle:

Fall 1: $|v x y|_{c}=0$

$|v x y|_{\textcolor{pink}{c}}=0 \wedge |v y| \geq 1 \implies|v y|_{\textcolor{pink}{a}}+|v y|_{\textcolor{pink}{b}}>0$

Wir wählen ein beliebiges $i=0$ .

$w_{0}=u v^{0} x y^{0} z=u x z$

Dem pumping Lemma zufolge müsste $w_0 \in L$

Für $uxz$ gilt:

$|u x z|_{\textcolor{pink}{a}}<|w|_{\textcolor{pink}{a}}$

$|u x z|_{\textcolor{pink}{b}}<|w|_{\textcolor{pink}{b}}$

$|u xz|_{\textcolor{pink}{c}}=|u v x y z|_{\textcolor{pink}{c}}=|w|_{\textcolor{pink}{c}}$

Das widerspricht $|u x z|_{\textcolor{pink}{a}}=|u x z|_{\textcolor{pink}{b}}=|u x z|_{\color{pink}c}$ und daraus folgt $u x z = w_0\notin L$ .

Fall 2: $|v x y|_{c}>0$

$|v x y|_{\color{pink}c}>0 \wedge |v y| \geq 1\implies |v x y|_{\color{pink}a}=0 \wedge |v y|_{\color{pink}b}+|v y|_{\color{pink}c}>0$

Wir wählen ein beliebiges $i=0$ .

$w_{0}=u v^{0} x y^{0} z=u x z$

Für $uxz$ gilt:

$|u x z|_{\color{pink}a}=|u v x y z|_{\color{pink}a}=|w|_{\color{pink}a}$

$|u x z|_{\color{pink}b}<|w|_{\color{pink}b}$

$|u x z|_{\color{pink}c}<|w|_{\color{pink}c}$

Das widerspricht $|u x z|_{\color{pink}a}=|u x z|_{\color{pink}b}=|u x z|_{\color{pink}c}$ und daraus folgt $u x z \notin L$ .

Sprachfamilien

Die Menge aller formalen Sprachen $L \subseteq \Sigma^{*}$ die von einer Typ- $i \in\{0,1,2,3\}$ Grammatik erzeugt werden können nennt man $\mathcal{L}_{i}(\Sigma)$ .

Die Familie nennt man $\mathcal{L}_i$ .

Typ-0:A→b,A→BC,AD→BC,b∈T∪{ε}Typ-1:A→b,A→BC,AD→BC,b∈TTyp-2:A→b,A→BC,b∈TTyp-3:A→b,A→bC,b∈T\begin{array}{lll} \text { Typ-0: } & A \rightarrow b, \quad A \rightarrow B C, \quad A D \rightarrow B C, & b \in T \cup\{\varepsilon\} \\ \text { Typ-1: } & A \rightarrow b, \quad A \rightarrow B C, \quad A D \rightarrow B C, & b \in T \\ \text { Typ-2: } & A \rightarrow b, \quad A \rightarrow B C, & b \in T \\ \text { Typ-3: } & A \rightarrow b, \quad A \rightarrow b C, & b \in T \end{array}Typ-0:Typ-1:Typ-2:Typ-3:A→b,A→BC,AD→BC,A→b,A→BC,AD→BC,A→b,A→BC,A→b,A→bC,b∈T∪{ε}b∈Tb∈Tb∈T

Für $\small 1,2,3$ ist $S \rarr \varepsilon$ erlaubt wenn $S$ nicht auf rechten Seite der Produktion ist.

$\mathcal L_0$ rekursiv aufzählbar

$\mathcal L_1$ kontextsensitiv

$\mathcal L_2$ kontextfrei

$\mathcal L_3$ regulär

Rekursive Sprachen $\mathcal{L}_{\text {rec }}(\Sigma)$

$L \in \mathcal{L}_{0}(\Sigma)$ ist rekursiv,

wenn $\Sigma^{*}-L= \bar{L} \in \mathcal{L}_{0}(\Sigma)$ ist.

Wortproblem

Das Problem $w \in L$ ist für rekursive Sprachen entscheidbar.

Beweis

Berechne schrittweise alle möglichen Wörter in $n$ Ableitungsschritten in Grammatik $G$ bzw $G'$ für das Komplement der Sprache.

Abschlusseigenschaften

L3L2L1L0VereinigungjajajajaKonkatenationjajajajaKleenescher SternjajajajaKomplementjaneinjaneinDurchschnittjaneinjajaDurchschnitt mit reg. MengenjajajajaHomomorphismenjajaneinjaε-freie Homomorphismenjajajajainverse Homomorphismenjajajajagsm-Abbildungenjajaneinjaε-freie gsm-Abbildungenjajajaja\small \begin{array}{|l|l|l|l|l|}\hline & \mathcal{L}_{3} & \mathcal{L}_{2} & \mathcal{L}_{1} & \mathcal{L}_{0} \\\hline \text { Vereinigung } & \text { ja } & \text { ja } & \text { ja } & \text { ja } \\\hline \text { Konkatenation } & \text { ja } & \text { ja } & \text { ja } & \text { ja } \\\hline \text { Kleenescher Stern } & \text { ja } & \text { ja } & \text { ja } & \text { ja } \\\hline \text { Komplement } & \text { ja } & \text { nein } & \text { ja } & \text { nein } \\\hline \text { Durchschnitt } & \text { ja } & \text { nein } & \text { ja } & \text { ja } \\\hline \text { Durchschnitt mit reg. Mengen } & \text { ja } & \text { ja } & \text { ja } & \text { ja } \\\hline \text { Homomorphismen } & \text { ja } & \text { ja } & \text { nein } & \text { ja } \\\hline \varepsilon \text {-freie Homomorphismen } & \text { ja } & \text { ja } & \text { ja } & \text { ja } \\\hline \text { inverse Homomorphismen } & \text { ja } & \text { ja } & \text { ja } & \text { ja } \\\hline \text { gsm-Abbildungen } & \text { ja } & \text { ja } & \text { nein } & \text { ja } \\\hline \varepsilon \text {-freie gsm-Abbildungen } & \text { ja } & \text { ja } & \text { ja } & \text { ja } \\\hline\end{array}VereinigungKonkatenationKleenescher SternKomplementDurchschnittDurchschnitt mit reg. MengenHomomorphismenε-freie Homomorphismeninverse Homomorphismengsm-Abbildungenε-freie gsm-AbbildungenL3jajajajajajajajajajajaL2jajajaneinneinjajajajajajaL1jajajajajajaneinjajaneinjaL0jajajaneinjajajajajajaja

Chomsky-Hierarchie

SprachfamilieGrammatiktypMaschinenmodellL0unbeschra¨nktTuringmaschine (TM)L1kontextsensitiv / monotonLinear besch. Aut. (LBA)L2kontextfreiKellerautomat (KA)L3regula¨rEndlicher Automat (EA)\small \begin{array}{l|l|l}\text { Sprachfamilie } & \text { Grammatiktyp } & \text { Maschinenmodell } \\\\\hline \hline \begin{array}{l} \mathcal{L}_{0} \end{array} & \color{grey}\text { unbeschränkt } & \begin{array}{l}\text { Turingmaschine (TM)}\end{array} \\\hline \begin{array}{l}\mathcal{L}_{1} \end{array} & \text { kontextsensitiv / monoton} & \begin{array}{l}\text { Linear besch. Aut. (LBA)}\end{array} \\\hline \begin{array}{l}\mathcal{L}_{2} \end{array} & \text { kontextfrei } & \begin{array}{l}\text { Kellerautomat (KA)}\end{array} \\\hline \begin{array}{l}\mathcal{L}_{3} \end{array} & \text { regulär } & \begin{array}{l}\text { Endlicher Automat (EA)}\end{array} \end{array}SprachfamilieL0L1L2L3Grammatiktypunbeschra¨nktkontextsensitiv / monotonkontextfreiregula¨rMaschinenmodellTuringmaschine (TM)Linear besch. Aut. (LBA)Kellerautomat (KA)Endlicher Automat (EA)

$\small \mathcal{L}_{3} \varsubsetneqq \mathcal{L}_{2} \varsubsetneqq \mathcal{L}_{1} \varsubsetneqq \mathcal{L}_{r e c} \varsubsetneqq \mathcal{L}_{0}$

$\mathcal L_0$ rekursiv aufzählbar

$\mathcal L_{rec}$ rekursiv

$\mathcal L_1$ kontextsensitiv

$\mathcal L_2$ kontextfrei

$\mathcal L_3$ regulär

Homomorphismen

Alphabete: $\Sigma, \Gamma$

Homomorphismus: $h: \Sigma \mapsto \Gamma^{*}$

$h(\varepsilon)=\varepsilon$ (wenn $\forall a \in \Sigma: h(a) \neq \varepsilon$ dann nennt man ihn $\varepsilon$ -frei)

$h(w a)=h(w) h(a)$

Anwendung auf jedes Wort der Sprache

$h(L)=\{h(w) \mid w \in L\}$

Inverser Homomorphismus

$h^{-1}(L):=\left\{w \in \Sigma^{*} \mid h(w) \in L\right\}$

Abgeschlossenheit unter $h(L)$

Sprachfamilien $\small 0,2,3$ sind gegenüber beliebigen Homomorphismen abgeschlossen.

Familie der monotonen, kontextsensitiven Sprachen ist nur gegenüber $\varepsilon$ -freien Homomorphismen abgeschlossen.

Abgeschlossenheit unter $h^{-1}(L)$

Sprachfamilien $\small 0,1,2,3$ gegenüber inversen Homomorphismen abgeschlossen.

GSM-Abbildungen

Generalized sequential machines GSM

endlicher Automat mit Ausgabe

$M=\left\langle Q, \Sigma, \Gamma, \delta, q_{0}, F\right\rangle$

$Q$ Zustände

$\Sigma$ Eingabealphabet

$\Gamma$ Ausgabealphabet

$\delta: Q \times \Sigma \rightarrow Q \times \Gamma^{*}$

Beispiel für Übergang

$\delta(q, a)=(p, w)$

Zustandswechsel $q \mapsto a$ und es wird $w$ ausgegeben.

GSM Abbildungen

$f_{M}: \Sigma^{*} \rightarrow \mathcal{P}\left(\Gamma^{*}\right)$

$f_{M}(L):=\left\{v \in \Gamma^{*} \mid v \in f_{M}(w) \text { für ein } w \in L\right\}$

Mann nennt $M$ und $f_M$

$\varepsilon$ -frei

wenn $\delta: Q \times \Sigma \rightarrow Q \times \Gamma^{+}$

deterministisch

wenn für jedes $(q, a)$ höchstens ein $(q, a ; p, v) \in \delta$ existiert.

Homomorphismus vs. GSM-Abbildung

Homomorphismen = GSM-Abbildungen mit 1 Zustand.

$M_{h}=(\{q\}, \Sigma, \Gamma, \delta, q,\{q\})$

$\forall a \in \Sigma: \delta(q, a)=(q, h(a))$

Abschluss von Familien $\mathcal L_i$ gegenüber GSM

Sprachfamilien $\small 0,2,3$ sind gegenüber beliebigen GSM-Abbildungen abgeschlossen.

Kontextsensitive Sprachen nur gegenüber $\varepsilon$ -freien GSM-Abbildungen.