cards-deck: university::theo_complexity date-created: 2024-02-21 12:07:35 date-modified: 2024-09-22 02:47:20

Grammatiken

part of [[112.00_anchor_overview]]

Overview

Chomsky ist noch die einzig lebende Person, die hier betrachtet und relevant ist, weil er eine Hierarchie von verschiedenen Grammatiken erörtert / gefunden hat.

Historische betrachte von Informatik: -> Es war damals schon eine zentrale Frage, warum Maschinen genau, wie Menschen, Sprache verstehne und verarbeiten können.

[!Tip] Wie schwer ist menschliche Sprache?

Grammatiken sind eine weitere Technik, um Sprachen zu beschreiben. Sie kommen aus der Linguistik und beschreiben die Erzeugung von Sätzen durch Regeln und Variablen, in die am Schluss Wörter eingesetzt und so Sätze und Satzstrukturen erstellt werden können.

Eine mögliche Grammatik für einfache Sätze: ![[Pasted image 20230503225725.png|448]] oder aber auch folgende Struktur:

$R \subset V \times (V \cup Σ)$ auf der linken Seite sitzt nur ein Wort / eine Variable!, und auf der rechten Seite kann eine Variable

Wir finden eine Variable und gemäß der Regeln können wir die dann übersetzen. Dabei ist es irrelevant, was sich um diese Variable befindet – also Literale oder andere Variablen: Wir können diese Variable unabhängig des Kontextes jetzt ersetzen, gemäß der Regeln!

[!info] Diese Struktur erinnert an EBNF - die Enhanced Bakus Naurs-Form - die zur Beschreibung einer Programmiersprache genutzt wird!

Als Beispiel einer Grammatik Betrachte alle Wörter über dem Alphabet ${a, b}$ die durch die folgenden Regeln beschrieben werden:

Das leere Wort ist in $L$
Falls $x \in L$ , dann auch $a x b \in L$

Grammatik | Intuition

[!Intuition] Grammatik

Eine Grammatik ist ein Satz an Ersetzungsregeln, die man auch als die Produktion bezeichnet.

Eine Grammatik gibt dabei also an, wie man eine gewisse Struktur (vielleicht einen Ausdruck mit mehreren Variablen und Mustern, passend in einen validen Wert umschreiben kann (welcher durch die Produktionsregeln erzeugt wird))

Beispielhaft etwa: $> A > A > B \to 0 A 1 \to B \to # >$

_Unter Betrachtung der obigen Beispielssprache und Idee, wie ist eine Produktionsregel aufgebaut, in welche Teile gliedert sie sich? Wie kann man jetzt Wörter unter Betrachtung einer Grammatik erzeugen, welche wäýen in der obigen Grammatik möglich? #card

Eine Produktionsregel baut sich also darauf auf, dass sie links eine Variable stehen hat und rechts einen String bestehend aus Variablen und Terminalen (was einfach Symbole des Alphabets sind, etwa a,b,c, (keine Variablen!))

Unter Dieser Vorbetrachtung kann man dann eine Grammatik folgend nutzen, um Wörter zu erzeugen:

Beginne den String mit der Startvariable:

Finde im String, der von der Startvariable erzeugt wird, eine weiter Variable, zu welcher eine Produktion existiert und ersetze sie mit dieser Regel!

Das wiederholen wir, bis wir keine Variablen mehr im String haben!

Im obigen Beispiel wären das etwa folgende Wörter: $0#1, 00#11, \dots$ da: $A \to 0 A 1 \to 00 A 110 \to 00 B 11 \to 00#11$

[!question]

Die Sprache, die von einer kontextfreien Grammatik erzeugt wird, nennen wir kontextfreie Sprache (context-free-language (CFL))

Grammatik | Definition

Während wir zuvor die Intuition und Idee einer Grammatik beschrieben haben, möchten wir sie nun formal definieren, sodass eine Beschreibung und Anwendung dieser möglich ist.

[!Definition]

Wir möchten jetzt ferner eine kontextfreie Grammatik definieren:

Wir beschreiben eine solche Grammatik mit einem 4-Tupel: $G = (V, Σ, R, S)$ wobei diese jeweils folgende Eigenschaften haben:

was beschreibt das Tupel?, Wie sind die Inhalte von $R$ aufgebaut und zu verstehen? #card

$V$ ist eine endliche Menge von Variablen (also es sind die Einträge, die wir später durch Terminal ersetzen werden)

$Σ$ beschreibt die endliche Menge von Terminalsymbolen. Wobei ferner gilt, dass sie sich nicht mit den Variablen-Beschreibungen überschneiden, also $Σ \cap V = \emptyset$ ( Grundlegend sind das also die niedrigsten Bausteine, die dann ein Wort wild, etwa a,b,c,d,e,f… (gleich zum Alphabet bei Sprachen))

$R \subset V \times (V \cup Σ)^{*}$ beschreibt die Regel (die Produktionsregeln), wobei hier einfach beschrieben wird, dass $R$ eine Teilmenge der Variablen ist und immer ein Tupel $R_{i} \to V_{i} V_{i_{2}} \dots Σ_{i}$ existiert (also eine Regel, wie aus einer Variable ein neuer Term erstellt wird)

$S \in V$ beschreibt die Startvariable!

Ferner beschreiben wir noch, $u \implies_{G}~ v$ “ $u$ geht unter $G$ (der Grammatik) unmittelbar über in $v$ ”, bei $u \in V, v \in (V \cup Σ)^{*}$ falls es eine Regel $y \to y^{'}$ in $R$ gibt und weiter $z, x \in (V \cup Σ)^{*}$ , sodass dann folgt: $u = x yz \land v = x y^{'} z$

Also wir haben eine Regel, die unseren Term nicht stark verändert, aber ihr einen neuen Inhalt / Wert gibt.

Wir schreiben ferner $u \implies_{G}^{*} ~v$ (also einfach, dass man von u nach v kommen kann), wenn es eine Folge von Schritten $u ⟹ u_{1} ⟹ u_{2} ⟹ \dots ⟹ v$ gibt, und sagen dann dass $v$ aus $u$ abgeleitet wird ( u in v übergeht)

Damit haben wir die Grundlage gesetzt und können jetzt beliebige Grammatiken beschreiben, aufbauen und damit Wörter und auch ganze Sprachen erzeugen!

Sprachen aus Grammatiken

Dass man jetzt eine Sprache mittels einer Grammatik beschreiben kann ist klar, da wir mit dieser ja eine gewisse Menge von Wörter erzeugen können.

[!Definition]

Se $G$ nun eine Grammatik

Wie beschreiben wir die erzeugte Sprache?was beschreibt die Satzform? #card

Die von $G$ erzeugte Sprache ist einfach beschrieben mit $L(G) = { w \in \Sigma^{}\mid S \implies_{G}^{} ~w }$ ( also sie sit die Menge aller Wörter, die man von der Startvariable ableiten kann)

Man beschreibt eine Ableitung von $w_{n}$ ferner so, dass man sie von der Startvariable über diverse Umformungen erreichen kann, also $(w_{0}, w_{1}, \dots), w_{0} = S, w_{n} \in Σ^{*} \to w_{0} ⟹ w_{1} ⟹ \dots ⟹ w_{n}$

Wir nennen ein Wort das noch Variablen enthält eine Satzform

Beispiele

Wir betrachten in Aufgabe 2 Grammatiken diverse Grammatiken beispielhaft

Beispiel | Dyck-Sprache

Walther von Dyck (1856 - 1934, München)

[!Definition] DYCK-Sprache Die folgende Sprache bezeichnen wir als Dyck-Sprache: $D_{1}$ über $Σ = {[,]}$ Und somit beschreiben wir Sprachen, die beliebige Klammerpaare haben kann. $L_{Dyc k} = {u \in Σ^{*} ∣ alle Pr \overset{a}{¨} fixe von u enthalten h \overset{o}{¨} chsten so viele ], wie auch [, also ist die Zahl dieser gleich}$

Wie können wir diese Grammatik beschreiben? #card

$G = V = {S}, Σ = {[,]}, R, S$ und $R = {S \to ε ∣ [S] ∣ SS}$

Ein weiteres Beispiel:

$G := ({S}, {a, b}, P, S)$ wobei $P$ die Übergangsfunktion bzw gibt sie an, wie übersetzt werden kann. $P = {S \to a S b, S \to ab}$ Das heißt wir können die Variable $S$ mit einem der Literalen-Kombination $ab$ ersetzen

Formal können wir die Grammatik unter Verwendung von Ableitungsregeln beschreiben: $X ⟶ a X b$

[!idea] Jede Grammatik beschreibt dabei eine Sprache, die Wörter die durch einen solchen Satz Regeln erzeugt werden können, zusammenfässt:

$L = {a^{n} b^{n} ∣ n \in N}$

Allgemeine Grammatiken

Wir haben uns bis jetzt nur Kontextfreie Grammatiken angeschaut, die also etwa keine kontext-sensitivien Grammatiken beschreiben können. Wir möchten also verallgemeinern:

[!Definition] Allgemeine Grammatiken

Wir beschreiben eine allgemeine Grammatik wieder mit einem 4-Tupel $G = (V, Σ, R, S)$ und geben dieser folgende Eigenschaften:

Wie beschreiben wir die vier Parameter diesmal? Was ist der Unterschied zur allgemeinen Grammatik? #card

$V$ ist eine endliche Menge von Variablen

$Σ$ ist eine endliche Menge von Terminalsymbolen. Wieder gilt $Σ \cap V = \emptyset$

$R \subset ((V \cup Σ)^{*} ∖ ε) \times (V \cup Σ)^{*}$ (Also wir erlauben jetzt auch, dass auf der linken Seite Terminalsymbole stehen können!)

Durch diese Konstruktion der Regeln erlauben wir jetzt dass eine Ersetzung durch einen vorher geschaffenen Kontext (also Buchstaben, die da aufgetreten sind (etwa $aaa X \to bbbY$ , wir vertauschen 3 gegen 3 b)) passieren bzw modelliert werden kann.

Das ist der Unterschied zu Kontextfreien Grammatiken: -> Ihre Produktion ersetzt nur Variablen mits String, kann dabei aber keinen Kontext - der durch die Terminal gegeben werden könnte - erkennen / anwenden

Chomsky-Hierarchie:

[!Feedback] Motivation

Wir sehen hier jetzt schon, dass kontextfreie Grammatiken wahrscheinlich weniger modellieren und erzeugen können, weil ihnen die Möglichkeit vom Kontext nicht gegeben ist.

Diese Hierarchie kann man jetzt durch ein linguistisches Modell von Chomsky besser beschreiben:

![[Pasted image 20230503230143.png]]

[!Definition] Chomsky-Hierarchie

Grundlegend schränkt die Chomsky-Hierarchie Grammatiken aufgrund der Form ihrer Regeln ein und gibt ihnen eine hierarchische Einordnung.

Eine Grammatik $G = (V, Σ, R, S)$ ist vom Typ $i$ , falls alle Regeln in $R \subset ((V \cup Σ) ∖ ε)^{*} \times (V \cup Σ)^{*}$ der Form $w_{1} \to w_{2}$ sind und folgende Parameter / Einschränkungen aufweisen: Wir unterteilen in 0-4 Typen!

Was sind die Eigenschaften die für folgende Typ 0,1,2,3 Grammatiken gelten müssen? Welche Aussnahme erlauben wir ferner? #card

Typ 0 hat keine Einschränkung (allgemeine Grammatik)

Typ 1 gibt an, dass $∣ w_{1} ∣ \leq ∣ w_{2} ∣$ ( also von unserem Start-Wort können wir nicht kleiner werden, sondern nur noch mehr hinzufügen)

Typ 2 gibt an, dass sie Typ 1 und $w_{1} \in V$ ist ( also wir fangen bei einer Variable an und erhalten anschließend einen String von Terminalen und auch Variablen) (wir haben “links” niemals eine Variable stehen) (kontextfreie Grammatik)

Typ 3 gibt an, dass sie Typ 2 und $w_{2} \in Σ \cup Σ V$ ist –> Also sie folgt der strikten Struktur, dass man nur Zwischenformen der erzeugen können, wo links Terminale und rechts eine Variable steht! (dann ist sie Links-erzeugend)

( Es gilt die Sonderregel, dass $S \to ε$ erlaubt ist, man also ein leeres Wort direkt erzeugen kann)

Eine Sprache $L \subseteq Σ^{*}$ heißt jetzt vom Typ $i$ , wenn es also eine Grammatik vom Typ $i$ gibt, die sie erzeugen kann.

[!Important] Erkenntnis der Hierarchie Die Erkenntnis über diese Hierarchie war ein immenser Durchbruch, weil somit erkennen werden konnte, das man diverse Inhalte anders darstellen und translatieren konnte. Ferner ist es also technisch möglich sehr komplexe Sprachen doch erzeugen / darstellen zu können!

Reguläre Grammatiken

[!Definition]

Womit beschreiben wir eine reguläre Grammatik, was folgt dazu mit regulären Sprachen? #card

Eine reguläre Grammatik ist also eine Grammatik mit Produktionen der Form:

$A \to a \lor A \to a B$ (Das heißt man baut nach und nach ein Wort auf, was maximal am rechten Ende eine Variable stehen hat, sonst sind es nur Terminal!)

Zu jeder regulären Sprache gehört eine reguläre Grammatik!

Die Menge aller Sprachen die von regulären Grammatiken erzeugt werden, ist genau $REG$ 112.03_reguläre_sprachen (sowie reguläre Ausdrücke oder endliche Automaten)

Zu jedem DFA gehört eine reguläre Grammatik:

[!Satz]

Jede reguläre Sprache - alle die von DFAs erkannt werden - sind von Typ3-Grammatiken erzeugbar:

Wie zeigen wir das? #card

Sei $L \subseteq Σ^{*}$ eine Sprache und ferner $M = (Q, Σ, δ, q_{0}, F)$ ein DFA der die Sprache erzeugt.

Ein Wort $x \in L (M)$ ist genau dann in der Sprache, wenn man nach einer Folge vom Startzustand über die Berechnung von $x$ in einen Endzustand fallen wird.

Weiterhin muss gelten: Es gibt eine Folge von Zuständen $q_{0}, q_{1}, \dots, q_{n}$ mit $z_{n} \in F$ und ferner haben wir Übergangsfunktionen, die diese Berechnung darstellen kann. Es gibt dann jetzt eine Folge von Variablen $q_{0}, q_{1}, \dots, q) n \in V$ wobei der Startzustand: $q_{0} = S$ gleich der Startvariable ist!

Dadurch lässt sich bilden: $S ⟹ a_{1} z_{1} ⟹ a_{1} a_{2} z_{2} ⟹ \dots ⟹ a_{1} a_{2} \dots a_{n - 1} z_{n - 1} ⟹ a_{1} a_{2} \dots a_{n}$ und somit haben wir die Konstruktion durch Variablen gefunden. und somit $x \in L (G)$ !

Andere Richtung: $⟸$ Wir gehen von einer Grammatik aus und jetzt konstruieren wir jetzt einen DFA Dabei ist

$Q = {V \cup {X}}, X \neq \in V$ –> denn X wird der akzeptierende Zustand!

$q_{0} = {S}$

$F = {> {q_{0}, X} > {X} falls (S \to ε) \in P sonst ist ein Spezialfall! >$ Wir traversieren also nach und nach die Übergangsfunktion: und geben dann immer das entsprechende Symbol heraus und somit kann ein Wort verarbeitet und processed werden.

Chomsky Normalform

Dinge mit : Links Variable und rechts beliebige Menge von Variablen

[!Definition] Chomsky Normalform eine kontextfreie Grammatik ist in Chomsky Normalform (CNF), wenn alle Regeln von der Form: $> A \to BC > A \to a >$ Hierbei sind $a$ Terminalvariablen und $A, B, C$ beliebige Variablen (Aber wir bilden nie wieder auf die Startvariable ab)

wir haben also die Möglichkleit eine Konstruktion, die von vielen Variablen auf wenige abbildet, immer in eine bestimmte Minimalform umwandeln zu können.

Satz |

[!Satz]

Zu jeder kontextfreien Sprache $L$ gibt es eine kontextfreie Grammatik $G$ in CHomsky Normalform welche sie generieren kann.

Wie können wir das beweisen, welche Punkte muss man hierbei beachten? #card

Nur als Idee: Sei $G$ die allgemeine kontextfreie Grammatik welche die Sprache $L$ generiert. Wir finden eine Reihe von Umformungen zur Chomsky-Normalform folgend:

Wir fügen eine neue Startvariable ein, die auf die alte Startvariable zeigt (damit verhindern wir den Loop auf sich selbst)

wir entfernen alle Regeln der Form $A \to ε, A \to B$ (das sind unnötige Regeln, weil sie nur einen Variablennamen ersetzen). Dafür können wir auch neue Variablen einfügen.

Alle verbleibenden Regeln sind jetzt nur noch zu alng, also von der Form $A \to u_{1}, u_{2}, \dots, u_{k}$ wobei $u_{k}$ Variablen oder Terminale sind.

Diese können dann auch rekursive auf Chomsky Normalform gebracht werden indem wir sie mit neuen Variablen ersetzen.

[!Feedback] Nutzen der Normalform

Der Nutzen der Normalform ist, dass sie verschiedene Beweise vereinfachen kann, weil nur die beiden Arten von Regeln berücksichtigt werden müssen (und das verallgemeinert). Insbesondere Ableitungen in eine CNF-Grammatik kann man auch immer durch binäre Bäume darstellen!

Folglich möchten wir den Algorithmus dazu betrachten:

Konvertieren kontextfreier Grammatik zur Chomsky Normalform

Ferner betrachten wir hier einen Algorithmus welcher uns dabei hilft eine kontextfreie Grammatik in 5 Schritten zu der äquivalenten Chomsky-Normalform umwandeln zu können:

[!Satz] Algorithmus zum Umwandeln in eine Chomsky-Normalform:

Betrachten wir eine Grammatik der Form: $G = ({S, A}, {a, b}, P, S)$ mit $P = {S \to \dots A \to \dots}$

Wie gehen wir vor, um sie jetzt entsprechend in eine Chomsky-Normalform bringen zu können? Spezifisch möchten wir die 5 Schritte auflisten und erklären, warum sie umgesetzt werden #card

neue Startvariable einfügen Da wir verbieten, dass die Startvariable auf sich selbst zeigt, fügen wir eine neue ein $S_{0}$ welche dann auf die alte zeigt, sodass die Grundsemantik der Grammatik nicht verletzt wird. Also $S_{0} \to S, S \to \dots$

löschen von Regeln der Form $A \to ε$ , $A \neq = S_{0}$ Wir wollen bei der Normalform nur zulassen, dass die Startvariable auf das leere Wort abbilden kann. Ferner werden wir also alle Übergänge einer Variable / eines Nicht-Terminal in $ε$ terminieren bzw. entfernen. Anschließend müssen wir aber die neue Struktur bei allen anderen Regeln anpassen. Wenn jetzt $A \to ε$ gestrichen wurde, dann werden Regeln, wie $B \to a A bb A$ anders aussehen können. Wir müssen also jetzt für jede Regel, die die Entfernten beinhaltet die Form anbringen, wenn sie $ε$ wäre / also leer. Das heißt, dass etwa für $A \to ε ∣ b$ folgend adaptiert wird: $B \to a A bb A$ wird zu $B \to abb A ∣ a A bb A ∣ a A bb ∣ abb$ (also die Kombinationen, wo $A$ eventuell leer wäre)

Löschen von Terminalen auf sich zeigend: $A \to B$ Bei der Normalform möchten wir keine Formen haben, wo ein Nicht-Terminal auf einen einzelnen anderen zeigt, sondern nur $A \to BC$ o.ä. Demnach möchten wir jetzt alle Regeln der Form $A \to B$ entfernen und dann $A$ so ausbauen, dass es die Übergänge von $B$ einfach übernimmt. -> Wir komprimieren also doppelte Übergänge, die keinen Mehrwert in der Betrachtung bieten. Also Für ein $A \to B, B \to u_{1} ∣ u_{2} ∣ \dots$ wird dann $A \to u_{1} ∣ u_{2} ∣ \dots$ und die vorherigen von $A$

Ersetzen von langen Verkettungen $k \geq 3$ Wir möchten jetzt Regeln der Form $A \to u_{1} u_{2} u_{3} \dots u_{k}$ mit $k \geq 3$ bzw aufteilen. Dafür werden wir sie in folgende Form aufteilen und entsprechend neue Variablen einfügen: $A \to u_{1} A_{1}, A_{1} \to u_{2} A_{2}, A_{2} \to u_{3} A_{3} \dots$ also wir splitten in Teile von $a A_{k}$ auf, sodass wir der Struktur der Normalform näher kommen!

Entfernen von Nicht-Terminalen/Terminalen Verbindungen Es kann jetzt noch auftreten, dass ein Übergang $A \to a A$ auftritt, also hier auf der “rechten Seite” ein Terminal und Nicht-Terminal steht. Das wird in der Normalform nicht erlaubt, weil wir ja nur 2er-Verkettungen von Variablen und sonst einzelne Terminale erlauben. Das heißt jetzt, dass wir folgend einfach jeden Terminal mit einem neuen Zustand ersetzen, der auf den Terminal zeigt: Also $A \to a B ⟹ V_{a} \to a, A \to V_{a} B$

Wir können jetzt herausfinden, dass es auch in Kontextfreien-Sprachen ein Pumping-Lemma gibt. Also wir werden sehen, dass auch kontextfreie Sprachen in ihrer Mächtigkeit der Konstruktion und Darstellung limitiert sind und wir somit auch ans Limit stoßen!

[!Definition] Vereinigung

Es gilt: Wenn $L_{1}, L_{2}$ kontextfrei sind, so ist es auch $L_{1} \cup L_{2}$

Wie können wir das beweisen? #card

Seien die beiden Grammatiken, die die Sprachen erzeugen $G_{1} = (V_{1}, Σ, R_{1}, S_{1}), G_{2} = (V_{2}, Σ, R_{2}, S_{2})$ Wir konstruieren nun eine neue Grammatik $G = (V, Σ, R, S)$ mit $V = V_{1} \cup V_{2} \cup {S}$ (als neue Starvariable) und ferner $R = R_{1} \cup R_{2} \cup {S \to S_{1}, S \to S_{2}}$ (also wir gehen vom Start entweder in den Start von $L_{1} \lor L_{2}$ ! )

Dann ist offensichtlich $L (G) = L_{1} \cup L_{2}$

Schnitt:

[!hinweis] Schnitt

Es gibt kontextfreie Sprachen $L_{1}, L_{2}$ für die $L_{1} \cap L_{2}$ nicht kontextfrei ist (Also sind sie da nicht abgeschlossen!)

Wie zeigen wir das? #card

Betrachten wir etwa $L_{1} = {a^{n} b^{n} c^{m} ∣ n, m > 0}, L_{2} = {a^{m} b^{n} c^{n} ∣ n, m > 0}$ Dann ist $L_{1} \cap L_{2} = {a^{n} b^{n} c^{n} ∣ n > 0}$ was genau die nicht kontextfreie Sprache ist, wie wir zuvor gezeigt haben!

[!Important] $\exists$ Kontextfreie Sprachen mit nicht kontextfreien Komplement. Es gibt kontextfreie Sprachen, deren Komplement nicht kontextfrei ist Es folgt aus der Umformung: $L_{1} \cap L_{2} = \overline{\overline{L_{1}} \cup \overline{L_{2}}}$

Also das Komplement kann dann plötzlich nicht mehr kontextfrei sein. Die alte Konstruktion, dass man einfach die Zustände mit den akzeptierenden vertauscht, wird bei dem neuen Automaten 112.09_kellerautomaten nicht funktionieren! –> denn einen Speicher kann man nicht einfach invertieren –> was wäre das Komplement eines Wortes??

Stellen sie sich vor, es ist 1956 und sie müssen einen neuen Rechner erfinden, der das zeigen / konstruieren kann. Also eine nicht-kontextfreie Sprache, die das bearbeiten / erkennen kann.

Further:

und nun geht es weiter mit Turing-Maschinen, um die mächtigsten Automaten beschreiben zu können [[theo2_TuringMaschineBasics]]

scattered-lenity