Reguläre und kontextfreie Grammatiken: Grundlagen, Ableitung und Vereinfachung

Kontextunabhängige Sprachen

Reguläre Grammatiken (GR)

Die regulären Sprachen (LR) sind ein besonderer Fall von Sprachen, die unabhängig von ihrem Kontext sind. Sie sind Teil der Sprachen, die durch Automaten generiert werden können (LR $\to$ reguläre Ausdrücke, Endliche Automaten (AF); LIC $\to$ kontextfreie Grammatiken, Kellerautomaten).

Definition einer Regulären Grammatik G

Eine Reguläre Grammatik $G$ ist ein 4-Tupel $G = (N, \Sigma, S, P)$, wobei:

• $\Sigma$ das Alphabet (Menge der Terminalsymbole) ist.
• $N$ die Menge der Nichtterminalsymbole ist.
• $S \in N$ das Startsymbol ist.
• $P$ die Menge der Produktionen (Substitutionsregeln) ist, die die Form $A \to w$ haben, wobei $A \in N$ und $w \in (\Sigma \cup N)^*$ folgende Anforderungen erfüllt:
  1. $w$ enthält maximal ein Nichtterminal.
  2. Wenn $w$ ein Nichtterminal enthält, muss dieses das äußerste rechte Symbol in $w$ sein (Rechtsreguläre Grammatik).

Die Sprache, die durch die reguläre Grammatik $G$ erzeugt wird, wird mit $L(G)$ bezeichnet: $L(G) = \{w \in \Sigma^* \mid S \stackrel{*}{\Rightarrow} w\}$.

• "$\to$" bedeutet "ersetzt durch".
• "$\,|$" bedeutet "oder".
• "$\Rightarrow$" bedeutet "Ableitungsschritt" oder "erzeugt".
• "$\stackrel{*}{\Rightarrow}$" bedeutet 0 oder mehr Ableitungsschritte.
• "$\stackrel{+}{\Rightarrow}$" bedeutet 1 oder mehr Ableitungsschritte.
• "$\stackrel{p}{\Rightarrow}$" zeigt das Ergebnis nach $p$ Ableitungsschritten.

Reguläre Grammatiken (GR) und Endliche Automaten (AF)

Angenommen, $L$ ist eine Reguläre Sprache (LR). Eine GR kann aus einem Endlichen Automaten $M = (Q, \Sigma, \delta, q_0, F)$ generiert werden, für den $L = L(M)$ gilt.

Konvertierung: AF $\to$ GR

Wir definieren die Grammatik $G = (N, \Sigma, S, P)$:

• $N = Q$ (Die Nichtterminale sind die Zustände des AF).
• $S = q_0$ (Das Startsymbol ist der Startzustand).
• $P$ wird wie folgt definiert:
  • $q \to a p$, wenn $\delta(q, a) = p$.
  • $q \to \epsilon$ (leeres Wort), wenn $q \in F$ (d.h., $q$ ist ein akzeptierender Zustand).

Konvertierung: GR $\to$ AF

Aus einer Regulären Grammatik $G = (N, \Sigma, S, P)$ kann ein Endlicher Automat $M = (Q, \Sigma, \delta, s, F)$ konstruiert werden, sodass $L(G) = L(M)$.

• $Q = N \cup \{f\}$, wobei $f$ ein neuer Endzustand ist.
• $s = S$ (Startsymbol).
• $F = \{f\}$.

Die Übergangsfunktion $\delta$ wird aus den Produktionen in $P$ wie folgt aufgebaut:

1. Wenn $A \to a_1 a_2 \dots a_n B$ eine Produktion in $P$ ist (wobei $B$ ein Nichtterminal ist), werden neue Zustände $q_1, q_2, \dots, q_{n-1}$ zu $Q$ hinzugefügt, und es entstehen folgende Übergänge: $\delta(A, a_1) = q_1$, $\delta(q_1, a_2) = q_2, \dots, \delta(q_{n-1}, a_n) = B$.
2. Wenn $A \to a_1 a_2 \dots a_n$ eine Produktion in $P$ ist (wobei $a_i \in \Sigma$), werden neue Zustände $q_1, q_2, \dots, q_{n-1}$ zu $Q$ hinzugefügt, und es entstehen folgende Übergänge: $\delta(A, a_1) = q_1$, $\delta(q_1, a_2) = q_2, \dots, \delta(q_{n-1}, a_n) = f$.

Satz: Eine Sprache $L$ ist regulär genau dann, wenn sie durch eine Reguläre Grammatik (GR) erzeugt wird.

Um aus einem AF eine GR zu konstruieren, gibt es zwei Hauptmethoden:

1. Man erhält den äquivalenten Deterministischen Endlichen Automaten (DFA) und konstruiert daraus die Grammatik.
2. Man leitet die regulären Ausdrücke ab, die mit dem AF assoziiert sind, und konstruiert daraus die Grammatik.

Kontextfreie Grammatiken (KFG/GIC)

Definition einer Kontextfreien Grammatik G

Eine Kontextfreie Grammatik (KFG) $G$ ist ein 4-Tupel $G = (N, \Sigma, S, P)$, wobei:

• $N$ eine endliche Menge von Nichtterminalsymbolen ist.
• $\Sigma$ das Alphabet (Menge der Terminalsymbole) ist.
• $S \in N$ das Startsymbol ist.
• $P$ die Menge der Produktionen ist, wobei jede Produktion die Form $A \to w$ hat, mit $A \in N$ und $w \in (N \cup \Sigma)^*$.

Die Sprache, die durch die KFG $G$ erzeugt wird, wird mit $L(G)$ bezeichnet und heißt Kontextfreie Sprache (KFS).

• Die Menge der Regulären Sprachen (LR) ist eine Teilmenge der Kontextfreien Sprachen (KFS).
• Jede Sprache, die durch eine Reguläre Grammatik (GR) erzeugt wird, ist kontextunabhängig.

Ableitungsbäume und Ambiguität

Es ist nützlich, ein Diagramm zu erstellen, das die Ableitung eines Strings zeigt, wobei dargestellt wird, wie jedes Nichtterminal zur endgültigen Zeichenkette aus Terminalsymbolen beigetragen hat.

Der Ableitungsbaum

Ein solcher Graph wird als Ableitungsbaum bezeichnet. Er wird für eine bestimmte Ableitung konstruiert, indem ein Wurzelknoten mit dem Startsymbol erstellt wird. Der Wurzelknoten hat Kindknoten für jedes Symbol auf der rechten Seite der Produktion, die verwendet wird, um das Startsymbol zu ersetzen. Jeder Kindknoten, der mit einem Nichtterminal beschriftet ist, hat wiederum Kindknoten, die den Symbolen der rechten Seite der Produktion entsprechen, die zur Ersetzung dieses Nichtterminals verwendet wird. Knoten, die keine Kinder haben (Blattknoten), müssen mit Terminalsymbolen beschriftet sein.

Ambiguität (Mehrdeutigkeit)

Manchmal kann eine Grammatik für die Ableitung eines Strings unterschiedliche Ableitungsbäume zulassen.

• Eine Grammatik ist mehrdeutig (unklar), wenn es zwei oder mehr deutlich unterschiedliche Ableitungsbäume für dieselbe Zeichenkette gibt.
• Eine Grammatik ist eindeutig, wenn für jeden String $w$ alle Ableitungen denselben Ableitungsbaum ergeben.
• Wenn eine mehrdeutige Grammatik vorliegt, kann man manchmal eine andere Grammatik finden, die dieselbe Sprache erzeugt (äquivalent ist), aber nicht mehrdeutig ist (dies ist nicht immer möglich).
• Wenn alle KFG für eine Sprache mehrdeutig sind, spricht man von einer inhärent mehrdeutigen Kontextfreien Sprache (KFS).

Ableitungsstrategien

• Bei einer Linksableitung wird immer das am weitesten links stehende Nichtterminal erweitert.
• Bei einer Rechtsableitung wird immer das am weitesten rechts stehende Nichtterminal erweitert.

Vereinfachung Kontextfreier Grammatiken (KFG)

Ziel ist es, eine Grammatik $G = (N, \Sigma, S, P)$ in eine äquivalente Grammatik $G' = (N', \Sigma, S, P')$ zu transformieren, sodass $L(G) = L(G')$.

Algorithmen zur Bereinigung

A) Eliminierung nutzloser Symbole

Schritt 1: Eliminierung von Nichtterminalen, die keine Terminalzeichen erzeugen

1. Initialisiere $N'$ für alle Nichtterminale $A$, sodass $A \to w \in P$ mit $w \in \Sigma^*$.
2. Initialisiere $P'$ mit jeder Produktion $A \to w$, für die $A \in N'$ und $w \in \Sigma^*$.
3. Wiederhole: Füge zu $N'$ alle Nichtterminale $A$ hinzu, für die eine Produktion $A \to w$ existiert, mit $w \in (\Sigma \cup N')^*$. Füge diese Regel auch zu $P'$ hinzu, bis keine neuen Nichtterminale mehr zu $N'$ hinzugefügt werden können. (Diese Schleife endet immer, da $N$ und $P$ endlich sind.)