4.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 4.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 4.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 4.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 4.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 4.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 4.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 4.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 4.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 4.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 4.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 4.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 4.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 4.1.7 Sei

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

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

Beweis. Produktionen vom Typ 2, also von der Form

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

einführen, jedes

durch

ersetzen und die Produktion

hinzufügen.

Produktionen der Form zu eliminieren ist etwas komplizierter. Die Idee ist, dass in einer von ausgehende Ableitung eines Wortes irgendwann zum ersten Mal eine Wortform vorkommen muss, die nicht ein einzelnes Nichtterminalsymbol ist, also mit . Wir definieren nun als neue Menge von Produktionen, die keine Produktionen von der Form enthalten.

Im vorhergehenden Beweis haben wir nicht formal gezeigt, dass gilt. Unser Kernargument war das etwas saloppe "irgendwann muss ja mal eine Produktion kommen, die nicht von der Form ist". Anstatt den Beweis formal durchzuführen, stellen wir uns lieber eine interessantere Frage: wie können wir die neuen Produktionen 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 und alle Produktionen mit durchgehen und überprüfen, ob gilt. Dies können wir beispielsweise überprüfen, indem wir die Mengen definieren, also die Menge derjenigen Nichtterminalsymbole, die sich in bis zu Schritten von aus ableiten lassen. Wir berechnen die iterativ wie folgt: Die Menge lässt sich also mit zwei geschachtelten for-Schleifen berechnen: eine über die und eine über die Produktionen . Um für alle zu berechnen, brauchen wir eine weitere for-Schleife. Wir berechnen nun für steigende , bis keine weitere Veränderung eintritt.

Beobachtung 4.1.8 Wenn

, dann ist

Da die Menge nur wachsen kann, gilt nach höchstens Schritten und somit Das geht auch aus einer anderen Überlegung hervor: wenn man überhaupt ableiten kann, dann auch in maximal Schritten, denn ansonsten kämen ja in der Ableitung ein Nichtterminal doppelt vor und man könnte abkürzen.

Übungsaufgabe 4.1.7 Sei

. Die Grammatik mit den Regeln

erzeugt die Sprache aller Wörter, die kein

enthalten. Die Grammatik

erzeugt die Wörter, die kein

enthalten. Die Grammatik

mit Startsymbol

und den Produktionen

erzeugt die Sprache aller Wörter, die kein

oder kein

enthalten.

Die Grammatik ist regulär, enthält aber Produktionen vom Typ 3, zum Beispiel . Schreiben Sie eine äquivalente Grammatik , die nur Produktionen von der Form und 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 4.1.8 Betrachten Sie die folgende Grammatik über

mit den Nichtterminalsymbolen

und den insgesamt

Produktionen

Schreiben Sie eine äquivalente Grammatik ohne Produktionen der Form . 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 4.1.9 Seien

und

zwei reguläre Sprachen. Dann ist

auch regulär.

Beweis. Unsere Strategie ist, reguläre Grammatiken

für

und

für

zu betrachten und daraus eine neue reguläre Grammatik

für

zu bauen. Aus

sollen also genau diejenigen Strings ableitbar sein, die in

oder

enthalten sind.

Seien nun und die beiden regulären Grammatiken. Wir gehen davon aus, dass , 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 einfach umbenennen. Wir erschaffen nun ein neues Startsymbol und bauen uns eine neue Grammatik, in dem wir die zwei neuen Regeln hinzufügen. Formal also In einer Ableitung aus müssen wir uns also im ersten Schritt entscheiden, ob wir nach oder nach gehen und somit ein Wort in oder eines in 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 4.1.10 (Kleenesche Hülle). Seien

zwei Sprachen. Die Verknüpfungssprache

ist definiert als

Lemma 4.1.11 Seien

und

zwei reguläre Sprachen. Dann ist

auch regulär.

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

für

und

für

. Ob die beiden Alphabete die gleichen sind, also beide

, oder zwei verschiedene, also

, ist nicht entscheidend, da wir im letzteren Fall

und

als Sprachen über dem Alphabet

betrachten können.

Wir führen nun wiederum ein neues Startsymbol ein und fügen die Regel hinzu. Es sollte nun klar sein, dass wir aus genau die Wörter der Form mit und ableiten können, also genau die in . Leider ist die Regel nicht regulär, da auf der rechten Seite zwei nichtterminale Symbole vorkommen.

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

Die Menge an Produktionen der Grammatik besteht dann aus den nach dieser Tabelle modifizierten Produktionen von , zusammen mit den (unmodifizierten) Regeln von . Das Startsymbol von ist .

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

Definition 4.1.12 Sei

. Die Sprache

ist die Menge

Insbesondere ist

und

. Die Menge

ist nun

also die Sprache der Wörter der Form

, wobei

beliebig und jedes

ist.

Lemma 4.1.13 Sei

eine reguläre Sprache. Dann ist

auch regulär.

Beweis. Sei

eine reguläre Grammatik für

. Wir könnten ein neues Startsymbol

einführen und

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

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

-Ableitung ab:

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

noch als Regel hinzu.

Übungsaufgabe 4.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 4.1.14 Sei

eine reguläre Sprache und

ein neues Terminalsymbol. Die Sprache aller nichtleeren Folgen von

-Wörten, die durch

separiert sind, also formal

ist wiederum regulär.

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

und Kleenesche Hülle

verwenden. Dennoch lohne es sich, explizit für

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

eine reguläre Grammatik für

. Die Grammatik

für

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

-Ableitung aufhört, dann wieder ein

anzuhängen und wieder mit

weiterzumachen. Also: wir beginnen mit

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

Für jede -Produktion der Form fügen wir hinzu.

Die neue Grammatik

ist eine erweitert reguläre Grammatik, da Regeln wie

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

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.