5.1 Reguläre Grammatiken

Reguläre Grammatiken sind eine Untermenge der kontextfreien Grammatiken. Sie sind einerseits mächtig genug, um viele Dinge modellieren zu können (zum Beispiel syntaktisch korrekte Emailadressen), andererseits restriktiv genug, um algorithmisch gut bearbeitbar zu sein. Insbesondere ist das Parsen von regulären Grammatiken immer in linearer Zeit möglich.

Definition 5.1.1 Eine kontextfreie Sprache

G = (Σ, N, P, S)

heißt regulär, wenn jede Produktion eine der folgenden vier Formen hat:

\begin{aligned} X & \to a Y \\ X & \to a \\ X & \to Y \\ X & \to ϵ \end{aligned}

Eine Sprache

L \subseteq Σ^{*}

heißt regulär, wenn es eine reguläre Grammatik

G

gibt, die sie erzeugt, also

L (G) = L

Beispiel 5.1.2 Die folgende Grammatik über dem Alphabet

Σ = {1}

, den nichtterminalen Symbolen

{E, O}

und den Regeln

\begin{aligned} E & \to 1 O | ϵ \\ O & \to 1 E \end{aligned}

erzeugt die Sprache

{ϵ, 11, 1111, 111111, \dots} = {1^{n} | n istgerade}

Beispiel 5.1.3 Die folgende Grammatik haben wir bereits im letzten Abschnitt kennengelernt. Sie ist nicht regulär:

\begin{aligned} S & \to A B \\ A & \to ϵ | a A \\ B & \to ϵ | b B . \end{aligned}

Sie ist nicht regulär, weil die erste Regel $S \to A B$ gegen die Definition regulärer Grammatiken verstößt. Allerdings können wir leicht eine reguläre Grammatik $G^{'}$ angeben, die die gleiche Sprache erzeugt:

\begin{aligned} S & \to ϵ | a S | b T \\ T & \to ϵ | b T . \end{aligned}

Hier ist beispielsweise eine Ableitung des Wortes

a a b b b

\begin{array}{r} S \Rightarrow a S \Rightarrow a a S \Rightarrow a a b T \Rightarrow a a b b T \Rightarrow a a b b b T \Rightarrow a a b b b \end{array}

Wir sehen, dass wir eine Folge von $a$ 's erzeugen können, bei der ersten Produktion eines $b$ auf das Nichtterminal $B$ wechseln, welches dann ausschließlich weitere $b$ 's erzeugen kann.

Wir sehen: jede Wortform in der Ableitung besteht aus einer Folge von Terminalen, eventuell ganz am Schluss gefolgt von einem Nichtterminal. Halten wir diese erste Beobachtung formal fest.

Beobachtung 5.1.4 Sei

G = (Σ, N, P, S)

eine reguläre Grammatik und

S \Rightarrow^{*} α

eine Ableitung einer Wortform

α \in (Σ \cup N)^{*}

. Dann hat

α

die Form

y X

für

y \in Σ^{*}

und

X \in N \cup {ϵ}

Sie sollen nun an einer Reihe von Übungsaufgaben arbeiten, um ein Gefühl dafür zu bekommen, was reguläre Grammatiken tun können und was nicht.

Übungsaufgabe 5.1.1 Betrachten Sie die Gramatik über

Σ = {0, 1}

\begin{aligned} S & \to 1 S | 0 S | 0 \end{aligned}

Leiten Sie das Wort

11010

ab. Beschreiben Sie in eigenen Worten die erzeugte Sprache.

Übungsaufgabe 5.1.2 Betrachten Sie die Grammatik über

Σ = {0, 1}

\begin{aligned} A & \to 0 A | 1 A | 1 B \\ B & \to 0 C | 1 C \\ C & \to 0 D | 1 D \\ D & \to 0 E | 1 E \\ E & \to ϵ \end{aligned}

mit Startsymbol

A

. Leiten Sie das Wort

01101001

ab und beschreiben Sie die erzeugte Sprache in eigenen Worten.

Übungsaufgabe 5.1.3 Betrachten Sie das Alphabet

Σ = {1}

und die Sprache

L := {1^{n} | n ist durch 3 teilbar} .

Schreiben Sie eine reguläre Grammatik für

L

Übungsaufgabe 5.1.4 Betrachten Sie die Sprache

\begin{array}{r} L := {x \in {a, b}^{*} | in x kommt b mindestens 4 mal vor} \end{array}

und entwerfen Sie eine reguläre Grammatik für

L

Übungsaufgabe 5.1.5 Sei

Σ = {a, b, .}

und

L \subseteq Σ^{*}

die Sprache aller Strings der Form

x_{1} . x_{2} . x_{3} . \dots . x_{n}

wobei

n \geq 2

und jedes

x_{i} \in {a, b}^{+}

, also zum Beispiel a.bba.aba aber nicht aba und auch nicht a.b..a Entwerfen Sie eine reguläre Grammatik für diese Sprache.

Übungsaufgabe 5.1.6 Unsere Grammatik für korrekte Emailadressen im letzten Abschnitt war nicht regulär. Allerdings können wir eine reguläre Grammatik angeben, die die gleiche Sprache erzeugt.

Entwerfen Sie eine reguläre Grammatik für die Sprache aller korrekter Emailadressen über dem Alphabet $Σ = {a, b, ., -, @}$ . Sie dürfen natürlich noch weitere Buchstaben zulassen, dann schreiben Sie sich aber schnell zu Tode.

Erweitert reguläre Grammatiken

In einer Übungsaufgabe oben wurden Sie aufgefordert, eine reguläre Grammatik zu schreiben für die Sprache aller $1^{n}$ mit $n$ durch 3 teilbar. Hier ist eine besonders einfache Lösung:

\begin{array}{r} S \to ϵ | 111 S \end{array}

Sehen Sie, Sie können hier Einsen nur in Dreierblöcken erzeugen. Leider ist diese Grammatik nicht regulär nach unserer obigen Definition. Was tun wir, wenn wir nicht zufrieden sind mit einer Definition? Wir wandeln sie ab.

Definition 5.1.5 Eine Grammatik

G = (Σ, N, P, S)

heißt erweitert regulär, wenn jede Produktion eine der folgenden Formen hat:

\begin{aligned} X & \to α Y \\ X & \to α \end{aligned}

hat, wobei

X \in N

und

α \in Σ^{*}

ist. Im Unterschied zu den eigentlich regulären Grammatiken erlauben wir also mehrere terminale Symbole auf der rechten Seite, sofern Sie vor dem Nichtterminal vorkommen.

Theorem 5.1.6 Sei

G = (Σ, N, P, S)

eine erweitert reguläre Grammatik. Dann existiert eine reguläre Grammatik

G^{'} = (Σ, N^{'}, P^{'}, S)

, die die gleiche Sprache erzeugt:

L (G) = L (G^{'})

Beweis. Wir ersetzen einfach jede Regel der Form

X \to a_{1} a_{2} \dots a_{k} Y

durch

k

reguläre Regeln:

\begin{aligned} X & \to a_{1} X_{2} \\ X_{2} & \to a_{2} X_{3} \\ \dots \\ X_{k} & \to a_{k} Y \end{aligned}

wobei wir darauf achten, dass

X_{2}, \dots, X_{k}

"frische" Nichtterminalsymbole sind. Falls

α = ϵ

ist, so ist die Regel bereits in einer in regulären Grammatiken erlaubten Form:

X \to Y

oder

X \to ϵ

◻

Wir können nun, wenn wir reguläre Grammatik entwerfen wollen, die bequemeren erweitert regulären Sprachen verwenden; wenn wir Dinge über reguläre Grammatik beweisen wollen (oder deren Grenzen studieren wollen), können wir uns auf die eigentlichen regulären Grammatiken beschränken, da wir wissen, dass beide Definition eh gleich mächtig sind.

Reguläre Grammatiken vereinfachen

Das letzte Theorem erlaubt uns, eine Definition von regulären Grammatiken zu verwenden, die uns mehr erlaubt. Im Folgenden zeigen wir, wie man die Form der Grammatiken noch stärker einschränken kann, ohne dass Sie an Mächtigkeit einbüßen. Per Definition 4.1 hat jede Produktion in einer regulären Grammatik eine der folgenden vier Formen:

\begin{aligned} 1. X & \to a Y \\ 2. X & \to a \\ 3. X & \to Y \\ 4. X & \to ϵ \end{aligned}

Wir zeigen nun, dass man auf Produktionen der Form 2 und 3 verzichten kann.

Theorem 5.1.7 Sei

G = (Σ, N, P, S)

eine reguläre Grammatik. Dann gibt es eine äquivalente reguläre Grammatik

G^{'} = (Σ, N^{'}, P^{'}, S)

, die nur Regeln vom Typ 1 und 4 enthält.

Beweis. Produktionen vom Typ 2, also von der Form

X \to a

können wir leicht eliminieren, indem wir ein neues Nichtterminalsymbol

E \notin Σ \cup N

einführen, jedes

X \to a

durch

X \to a E

ersetzen und die Produktion

E \to ϵ

hinzufügen.

Produktionen der Form $X \to Y$ zu eliminieren ist etwas komplizierter. Die Idee ist, dass in einer von $X$ ausgehende Ableitung eines Wortes irgendwann zum ersten Mal eine Wortform $α$ vorkommen muss, die nicht ein einzelnes Nichtterminalsymbol ist, also $X \Rightarrow^{*} Y \Rightarrow α$ mit $α \notin N$ . Wir definieren nun $P^{'} := {X \to α | α ist kein einzelnes Nichtterminal,und es gibt Y \in N mit X \Rightarrow^{*} Y und Y \to α)}$ als neue Menge von Produktionen, die keine Produktionen von der Form $X \to Y$ enthalten. $◻$

Im vorhergehenden Beweis haben wir nicht formal gezeigt, dass $L (G^{'}) = L (G)$ gilt. Unser Kernargument war das etwas saloppe "irgendwann muss ja mal eine Produktion kommen, die nicht von der Form $X \to Y$ ist". Anstatt den Beweis formal durchzuführen, stellen wir uns lieber eine interessantere Frage: wie können wir die neuen Produktionen $P^{'}$ im konkreten Fall die Mengen berechnen? Dann das müssen wir ja tun, wenn wir eine solche Transformation durchführen wollen. Im Prinzip müssen wir alle Nichtterminale $X$ und alle Produktionen $Y \to α$ mit $α \notin N$ durchgehen und überprüfen, ob $X \Rightarrow^{*} Y$ gilt. Dies können wir beispielsweise überprüfen, indem wir die Mengen $\begin{array}{r} N_{k} (X) := {Y \in N | es gibt X_{1}, \dots, X_{l - 1} mit X \to X_{1} \to X_{2} \dots X_{l - 1} \to Y und l \leq k} \end{array}$ definieren, also die Menge derjenigen Nichtterminalsymbole, die sich in bis zu $k$ Schritten von $X$ aus ableiten lassen. Wir berechnen die $N_{k}$ iterativ wie folgt: $\begin{aligned} N_{0} (X) & := {X}, \\ N_{k + 1} (X) & := N_{k} \cup {Z \in N | es gibt Y \in N_{k} (X) mit Y \to Z} . \end{aligned}$ Die Menge $N_{k + 1} (X)$ lässt sich also mit zwei geschachtelten for-Schleifen berechnen: eine über die $Y \in N_{k}$ und eine über die Produktionen $Y \to Z$ . Um $N_{k + 1} (X)$ für alle $X \in N$ zu berechnen, brauchen wir eine weitere for-Schleife. Wir berechnen nun $N_{\geq k}$ für steigende $k$ , bis keine weitere Veränderung eintritt.

Beobachtung 5.1.8 Wenn

N_{k + 1} (X) = N_{k} (X)

, dann ist

N_{k} (X) = N_{k + 1} (X) = N_{k + 2} (X) = \dots

Da die Menge $N_{k}$ nur wachsen kann, gilt nach höchstens $n = | N |$ Schritten $N_{n} (X) = N_{n + 1} (X)$ und somit $N_{n} (X) = {Y \in N | X \Rightarrow^{*} Y} .$ Das geht auch aus einer anderen Überlegung hervor: wenn man überhaupt $X \Rightarrow Y$ ableiten kann, dann auch in maximal $| N |$ Schritten, denn ansonsten kämen ja in der Ableitung ein Nichtterminal doppelt vor und man könnte abkürzen.

Übungsaufgabe 5.1.7 Sei

Σ = {a, b, c}

. Die Grammatik mit den Regeln

A \to ϵ | b A | c A

erzeugt die Sprache aller Wörter, die kein

a

enthalten. Die Grammatik

B \to ϵ | a B | c B

erzeugt die Wörter, die kein

b

enthalten. Die Grammatik

G

mit Startsymbol

S

und den Produktionen

\begin{aligned} S & \to A | B \\ A & \to ϵ | b A | c A \\ B & \to ϵ | a B | c B \end{aligned}

erzeugt die Sprache aller Wörter, die kein

a

oder kein

b

enthalten.

Die Grammatik $G$ ist regulär, enthält aber Produktionen vom Typ 3, zum Beispiel $S \to A$ . Schreiben Sie eine äquivalente Grammatik $G^{'}$ , die nur Produktionen von der Form $X \to b Y$ und $X \to ϵ$ enthält.

Wir können zwar auf Produktionen vom Typ 2 und 3 verzichten. Dies hat allerdings seinen Preis, wie die folgende Übungsaufgabe zeigt:

Übungsaufgabe 5.1.8 Betrachten Sie die folgende Grammatik über

Σ = {a_{1}, a_{2}, \dots, a_{n}}

mit den Nichtterminalsymbolen

{S, A_{1}, A_{2}, \dots, A_{n}}

und den insgesamt

3 n - 1

Produktionen

\begin{aligned} S & \to a_{1} A_{1} | a_{2} A_{2} | a_{3} A_{3} | \dots | a_{n} A_{n} \\ A_{1} & \to a_{1} | A_{2} \\ \dots \\ A_{i} & \to a_{i} | A_{i + 1} \\ \dots \\ A_{n - 1} & \to a_{n - 1} | A_{n} \\ A_{n} & \to a_{n} \end{aligned}

Schreiben Sie eine äquivalente Grammatik ohne Produktionen der Form $X \to Y$ . Wieviele Produktion hat Ihre neue Grammatik?

Reguläre Sprachen nach Baukastenprinzip bauen

Eine schöne Eigenschaft von regulären Grammatiken ist, dass sie mächtig genug sind, um uns zu erlauben, die nach dem Baukastenprinzip zu komplizierteren Einheiten zusammenzufügen. Formate wie beispielsweise Emailadressen sind oft aufgebaut nach Mustern wie

Ding 1, dann Ding 2, wie beispielsweise Username, dann @, dann Domainname
Ding, bliebig oft wiederholt, wie beispielsweise eine beliebig lange Folge von Labels, mit . separiert.
Ding 1 oder Ding 2. Beispielsweise Bindestrich oder alphanumerisches Zeichen.

Lemma 5.1.9 Seien

L_{1}

und

L_{2}

zwei reguläre Sprachen. Dann ist

L_{1} \cup L_{2}

auch regulär.

Beweis. Unsere Strategie ist, reguläre Grammatiken

G_{1}

für

L_{1}

und

G_{2}

für

L_{2}

zu betrachten und daraus eine neue reguläre Grammatik

G

für

L_{1} \cup L_{2}

zu bauen. Aus

G

sollen also genau diejenigen Strings ableitbar sein, die in

L_{1}

oder

L_{2}

enthalten sind.

Seien nun $G_{1} = (Σ_{1}, N_{1}, P_{1}, S_{1})$ und $G_{2} = (Σ_{2}, N_{2}, P_{2}, S_{2})$ die beiden regulären Grammatiken. Wir gehen davon aus, dass $N_{1} \cap N_{2} = \emptyset$ , dass es also bei den nichtterminalen Symbolen keinen Zweifel gibt, zu welcher Grammatik sie gehören. Falls dies nicht der Fall sein sollte, können wir zum Beispiel die Symbole in $N_{2}$ einfach umbenennen. Wir erschaffen nun ein neues Startsymbol $S \notin N_{1} \cup N_{2}$ und bauen uns eine neue Grammatik, in dem wir die zwei neuen Regeln $\begin{aligned} S & \to S_{1} \\ S & \to S_{2} \end{aligned}$ hinzufügen. Formal also $G := (Σ_{1} \cup Σ_{2}, N_{1} \cup N_{2} \cup {S}, P_{1} \cup P_{2} \cup {S \to S_{1}, S \to S_{2}}, S) .$ In einer Ableitung aus $G$ müssen wir uns also im ersten Schritt entscheiden, ob wir nach $S_{1}$ oder nach $S_{2}$ gehen und somit ein Wort in $L_{1}$ oder eines in $L_{2}$ ableiten wollen.

◻

In einem nächsten Schritt werden wir zeigen, dass Konstrukte wie Ding 1, gefolgt von Ding 2 mit regulären Grammatiken realisierbar sind.

Definition 5.1.10 (Kleenesche Hülle). Seien

L_{1}, L_{2} \in Σ^{*}

zwei Sprachen. Die Verknüpfungssprache

L_{1} \circ L_{2}

ist definiert als

\begin{array}{r} L_{1} \circ L_{2} := {α β | α \in L_{1}, β \in L_{2}} . \end{array}

Lemma 5.1.11 Seien

L_{1}

und

L_{2}

zwei reguläre Sprachen. Dann ist

L_{1} \circ L_{2}

auch regulär.

Beweis. Wir im letzten Beweis nehmen wir uns eine reguläre Grammatik

G_{1} = (Σ, N_{1}, P_{1}, S_{1})

für

L_{1}

und

G_{2} = (Σ, N_{2}, P_{2}, S_{2})

für

L_{2}

. Ob die beiden Alphabete die gleichen sind, also beide

Σ

, oder zwei verschiedene, also

Σ_{1}, Σ_{2}

, ist nicht entscheidend, da wir im letzteren Fall

L_{1}

und

L_{2}

als Sprachen über dem Alphabet

Σ := Σ_{1} \cup Σ_{2}

betrachten können.

Wir führen nun wiederum ein neues Startsymbol $S \notin N_{1} \cup n_{2}$ ein und fügen die Regel $S \to S_{1} S_{2}$ hinzu. Es sollte nun klar sein, dass wir aus $S$ genau die Wörter der Form $α β$ mit $S_{1} \Rightarrow^{*} α$ und $S_{2} \Rightarrow^{*} β$ ableiten können, also genau die in $L_{1} \cup L_{2}$ . Leider ist die Regel $S \to S_{1} S_{2}$ nicht regulär, da auf der rechten Seite zwei nichtterminale Symbole vorkommen.

Wir müssen anders vorgehen. Wir ändern die Regeln von $G_{1}$ so ab, dass immer, wenn in einer $G_{1}$ -Regle die Ableitung endet, wir das Zeichen $S_{2}$ anhängen:

\begin{array}{r} \begin{array}{ll} Regel in G_{1} & wird zu \\ X \to a Y & X \to a Y \\ X \to a & X \to a S_{2} \\ X \to Y & X \to Y \\ X \to ϵ & Y \to S_{2} . \end{array} \end{array}

Die Menge an Produktionen der Grammatik $G$ besteht dann aus den nach dieser Tabelle modifizierten Produktionen $P_{1}$ von $G_{1}$ , zusammen mit den (unmodifizierten) Regeln von $G_{2}$ . Das Startsymbol von $G$ ist $S_{1}$ .

◻

In einem dritten Lemma werden wir zeigen, dass die Konstruktion Ding, beliebig oft wiederholt mit regulären Sprachen möglich ist.

Definition 5.1.12 Sei

L \subseteq Σ^{*}

. Die Sprache

L^{n}

ist die Menge

\begin{array}{r} L^{n} := {α_{1} α_{2} \dots α_{n} | α_{i} \in L \forall 1 \leq i \leq n} . \end{array}

Insbesondere ist

L^{1} = L

und

L^{0} = {ϵ}

. Die Menge

L^{*}

ist nun

\begin{array}{r} L^{*} := L^{0} \cup L^{1} \cup L^{2} \cup L^{3} \cup \dots \end{array}

also die Sprache der Wörter der Form

α_{1} α_{2} \dots α_{n}

, wobei

n

beliebig und jedes

α_{i} \in L

ist.

Lemma 5.1.13 Sei

L

eine reguläre Sprache. Dann ist

L^{*}

auch regulär.

Beweis. Sei

G = (Σ, N, P, S)

eine reguläre Grammatik für

L

. Wir könnten ein neues Startsymbol

S^{'}

einführen und

\begin{aligned} S^{'} & \to ϵ \\ S^{'} & \to S S^{'} \end{aligned}

als zwei neue Regeln einführen. Natürlich geht das nicht, denn

S^{'} \to S S^{'}

ist nicht erlaubt in regulären Grammatiken. Ähnlich wie im vorherigen Beweis fangen wir das Ende einer

G

-Ableitung ab:

\begin{array}{r} \begin{array}{ll} Regel in G & wird zu \\ X \to a Y & X \to a Y \\ X \to a & X \to a S \\ X \to Y & X \to Y \\ X \to ϵ & Y \to S . \end{array} \end{array}

Um überhaupt eine Ableitung beenden zu können, fügen wir

S \to ϵ

noch als Regel hinzu.

◻

Übungsaufgabe 5.1.9 Hier sehen Sie einen URL mit Query-String:

https://web1.hszg.de/modulkatalog/index.php?activTopic=3&activNav=2&stid=566&frei=1&kennz=suche&activCont=1

Der URL besteht aus mehreren Teilen:

Dem Protokoll. Hier ist das https; es kann aber auch http oder ftp sein.
Dem :// nach dem Protokoll.
Dem Domainnamen, hier web1.hszg.de.
Optional nun einem Pfad, hier /modulkatalog/index.php.
Falls ein Pfad enthalten ist, dann optional ein ?, gefolgt von einem Query-String; dieser besteht aus beliebig vielen, aber mindestens einem Paar der Form Key=Value, wobei die Paare mit einem & separiert sind.

Zeigen Sie, dass die Sprache der syntaktisch korrekten URLs (in dem gerade beschriebenen Format) regulär ist. Sie können entweder direkt eine reguläre Grammatik angeben oder mit dem Baukastenprinzip und den drei letzten Lemmas argumentieren.

Wir führen ein weiteres Baukastenwerkzeug ein, weil es in der Praxis recht häufig vorkommt.

Theorem 5.1.14 Sei

L \subseteq Σ^{*}

eine reguläre Sprache und

c \notin Σ

ein neues Terminalsymbol. Die Sprache aller nichtleeren Folgen von

L

-Wörten, die durch

c

separiert sind, also formal

\begin{array}{r} L^{'} := L \circ ({c} \circ L)^{*} \end{array}

ist wiederum regulär.

Beweis. Dies folgt sofort aus den vorherigen Theorem, weil wir nur Konkatenation

\circ

und Kleenesche Hülle

^{*}

verwenden. Dennoch lohne es sich, explizit für

L^{'}

eine Grammatik zu bauen. Es ist auch recht einfach. Sei

G = \(Σ, N, P, S)

eine reguläre Grammatik für

L

. Die Grammatik

G^{'}

für

L^{'}

hat die gleichen Nichtterminale und das gleiche Startsymbol, gibt uns aber zusätzlich die Möglichkeit, wenn eine

G

-Ableitung aufhört, dann wieder ein

c S

anzuhängen und wieder mit

S

weiterzumachen. Also: wir beginnen mit

P^{'} := P

, fügen aber noch weitere Produktionen hinzu. Nämlich:

Für jede $G$ -Produktion der Form $Y \to ϵ$ fügen wir $Y \to c S$ hinzu.

Für jede $G$ -Produktion der Form $Y \to a$ fügen wir $Y \to a c S$ hinzu.

Die neue Grammatik

G^{'}

ist eine erweitert reguläre Grammatik, da Regeln wie

Y \to a c S

auf der rechten Seite zwei Terminalsymbole haben. Wir müssen sie also erst noch in eine "richtig reguläre" umwandeln. In konkreten Anwendungne empfiehlt es dazu, die Nichtterminale von

G^{'}

umzubenennen, damit keien Verwechslungsgefahr droht.

◻

Wir können noch sehr viel mehr Operationen mit regulären Sprachen machen als Vereinigung, Konkatenation und Kleenesche Hülle. Beispielsweise Umkehrung und Komplement, also beispielsweise

Alle Emailadressen, von rechts nach links gelesen (Umkehrung);
Die Menge aller syntaktisch inkorrekten Emailadressen (Komplement).

Mit den Werkzeugen, die wir uns bis jetzt erarbeitet haben, können wir eine Grammatik für das Komplement nicht konstruieren. Wir brauchen etwas mehr Maschinerie.