TI2—Kapitel 5.1

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 = (\Sigma, N, P, S)$ heißt regulär, wenn jede Produktion eine der folgenden vier Formen hat:

\begin{align*} X & \rightarrow aY \\ X & \rightarrow a \\ X & \rightarrow Y \\ X & \rightarrow \epsilon \end{align*}

Eine Sprache $L \subseteq \Sigma^*$ 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 $\Sigma = \{1\}$, den nichtterminalen Symbolen $\{E,O\}$ und den Regeln

\begin{align*} E& \rightarrow 1O \ | \ \epsilon \\ O&\rightarrow 1E \end{align*}

erzeugt die Sprache $\{\epsilon, 11, 1111, 111111, \dots \}= \{1^n | n \textnormal{ ist gerade}\}$.

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

\begin{align*} S&\rightarrow A B \\ A&\rightarrow \epsilon \ | \ a A \\ B&\rightarrow \epsilon \ | \ b B \ . \\ \end{align*}

Sie ist nicht regulär, weil die erste Regel $S \rightarrow AB$ 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{align*} S&\rightarrow \epsilon \ |\ a S \ | \ b T \\ T& \rightarrow \epsilon \ | \ b T \ . \end{align*}

Hier ist beispielsweise eine Ableitung des Wortes $aabbb$:

\begin{align*} S \Rightarrow aS \Rightarrow aaS \Rightarrow aabT \Rightarrow aabbT \Rightarrow aabbbT \Rightarrow aabbb \end{align*}

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 = (\Sigma, N, P, S)$ eine reguläre Grammatik und $S \Rightarrow^* \alpha$ eine Ableitung einer Wortform $\alpha \in (\Sigma \cup N)^*$. Dann hat $\alpha$ die Form $y X$ für $y \in \Sigma^*$ und $X \in N \cup \{\epsilon\}$.

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 $\Sigma = \{0,1\}$:

\begin{align*} S&\rightarrow 1 S \ | \ 0 S \ | \ 0 \end{align*}

Leiten Sie das Wort $11010$ ab. Beschreiben Sie in eigenen Worten die erzeugte Sprache.

Übungsaufgabe 5.1.2 Betrachten Sie die Grammatik über $\Sigma = \{0,1\}$:

\begin{align*} A&\rightarrow 0 A \ | 1 A \ | 1 B \\ B&\rightarrow 0 C \ | 1 C \\ C&\rightarrow 0 D \ | 1 D \\ D&\rightarrow 0 E \ | 1 E \\ E& \rightarrow \epsilon \ \end{align*}

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 $\Sigma = \{1\}$ und die Sprache

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

Schreiben Sie eine reguläre Grammatik für $L$.

Übungsaufgabe 5.1.4 Betrachten Sie die Sprache

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

und entwerfen Sie eine reguläre Grammatik für $L$.

Übungsaufgabe 5.1.5 Sei $\Sigma = \{a,b,.\}$ und $L \subseteq \Sigma^*$ die Sprache aller Strings der Form

x_1 . x_2 . x_3 . \cdots . 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 $\Sigma = \{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{align*} S \rightarrow \epsilon \ | \ 111S \end{align*}

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 = (\Sigma, N, P, S)$ heißt erweitert regulär, wenn jede Produktion eine der folgenden Formen hat:

\begin{align*} X&\rightarrow \alpha Y \\ X&\rightarrow \alpha \\ \end{align*}

hat, wobei $X \in N$ und $\alpha \in \Sigma^*$ 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 = (\Sigma, N, P, S)$ eine erweitert reguläre Grammatik. Dann existiert eine reguläre Grammatik $G' = (\Sigma, N', P', S)$, die die gleiche Sprache erzeugt: $L(G) = L(G')$.

Beweis. Wir ersetzen einfach jede Regel der Form

X \rightarrow a_1 a_2 \dots a_k Y

durch $k$ reguläre Regeln:

\begin{align*} X& \rightarrow a_1 X_2 \\ X_2&\rightarrow a_2 X_3 \\ \dots \\ X_k& \rightarrow a_k Y \end{align*}

wobei wir darauf achten, dass $X_2, \dots, X_k$ "frische" Nichtterminalsymbole sind. Falls $\alpha = \epsilon$ ist, so ist die Regel bereits in einer in regulären Grammatiken erlaubten Form: $X \rightarrow Y$ oder $X \rightarrow \epsilon$.A$\square$

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 5.1.1 hat jede Produktion in einer regulären Grammatik eine der folgenden vier Formen:

\begin{align*} 1. \quad X&\rightarrow aY \\ 2. \quad X&\rightarrow a \\ 3. \quad X& \rightarrow Y \\ 4. \quad X&\rightarrow \epsilon \end{align*}

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

Theorem 5.1.7 Sei $G = (\Sigma, N, P, S)$ eine reguläre Grammatik. Dann gibt es eine äquivalente reguläre Grammatik $G' = (\Sigma, N', P', S)$, die nur Regeln vom Typ 1 und 4 enthält.

Beweis. Produktionen vom Typ 2, also von der Form $X \rightarrow a$ können wir leicht eliminieren, indem wir ein neues Nichtterminalsymbol $E \not \in \Sigma \cup N$ einführen, jedes $X \rightarrow a$ durch $X \rightarrow aE$ ersetzen und die Produktion $E \rightarrow \epsilon$ hinzufügen. Produktionen der Form $X \rightarrow Y$ zu eliminieren ist etwas komplizierter. Die Idee ist, dass in einer von $X$ ausgehende Ableitung eines Wortes irgendwann zum ersten Mal eine Wortform $\alpha$ vorkommen muss, die nicht ein einzelnes Nichtterminalsymbol ist, also $X \Rightarrow^* Y \Rightarrow \alpha$ mit $\alpha \not \in N$ . Wir definieren nun

P' := \{ X \rightarrow \alpha \ | \ \alpha \textnormal{ ist kein einzelnes Nichtterminal, und es gibt $Y \in N$ mit $X \Rightarrow^* Y$ und $Y \rightarrow \alpha$}) \}

als neue Menge von Produktionen, die keine Produktionen von der Form $X \rightarrow Y$ enthalten.A$\square$

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 \rightarrow 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 \rightarrow \alpha$ mit $\alpha \not \in N$ durchgehen und überprüfen, ob $X \Rightarrow^* Y$ gilt. Dies können wir beispielsweise überprüfen, indem wir die Mengen

\begin{align*} N_k(X) := \{ Y \in N \ | \ \textnormal{ es gibt } X_1,\dots, X_{l-1} \textnormal{ mit } X \rightarrow X_1 \rightarrow X_2 \cdots X_{l-1} \rightarrow Y \textnormal{ und } l \leq k \} \end{align*}

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{align*} N_0 (X)&:= \{X\} \ , \\ N_{k+1} (X)&:= N_k \cup \{Z \in N \ | \ \textnormal{ es gibt } Y \in N_k(X) \textnormal{ mit } Y \rightarrow Z \} \ . \end{align*}

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 \rightarrow 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 $\Sigma = \{a,b,c\}$. Die Grammatik mit den Regeln $A \rightarrow \epsilon \ | \ b A \ | \ c A$ erzeugt die Sprache aller Wörter, die kein $a$ enthalten. Die Grammatik $B \rightarrow \epsilon \ | \ a B \ | \ c B$ erzeugt die Wörter, die kein $b$ enthalten. Die Grammatik $G$ mit Startsymbol $S$ und den Produktionen

\begin{align*} S&\rightarrow A \ | \ B \\ A& \rightarrow \epsilon \ | \ b A \ | \ c A \\ B&\rightarrow \epsilon | \ a B \ | \ c B \end{align*}

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 \rightarrow A$. Schreiben Sie eine äquivalente Grammatik $G'$, die nur Produktionen von der Form $X \rightarrow bY$ und $X \rightarrow \epsilon$ 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 $\Sigma = \{a_1,a_2,\dots,a_n\}$ mit den Nichtterminalsymbolen $\{S, A_1, A_2, \dots, A_n\}$ und den insgesamt $3n-1$ Produktionen

\begin{align*} S&\rightarrow a_1 A_1 | a_2 A_2 | a_3 A_3 | \dots | a_n A_n \\ A_1&\rightarrow a_1 | A_2 \\ \dots \\ A_i&\rightarrow a_{i} | A_{i+1}\\ \dots \\ A_{n-1}&\rightarrow a_{n-1} | A_n \\ A_n&\rightarrow a_n \end{align*}

Schreiben Sie eine äquivalente Grammatik ohne Produktionen der Form $X \rightarrow 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 = (\Sigma_1, N_1, P_1, S_1)$ und $G_2 = (\Sigma_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 \not \in N_1 \cup N_2$ und bauen uns eine neue Grammatik, in dem wir die zwei neuen Regeln

\begin{align*} S&\rightarrow S_1 \\ S&\rightarrow S_2 \end{align*}

hinzufügen. Formal also

G := (\Sigma_1 \cup \Sigma_2, N_1 \cup N_2 \cup \{S\}, P_1 \cup P_2 \cup \{S \rightarrow S_1, S \rightarrow 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.A$\square$

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 \Sigma^*$ zwei Sprachen. Die Verknüpfungssprache $L_1 \circ L_2$ ist definiert als

\begin{align*} L_1 \circ L_2 := \{ \alpha \beta \ | \ \alpha \in L_1, \beta \in L_2\} \ . \end{align*}

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 = (\Sigma, N_1, P_1, S_1)$ für $L_1$ und $G_2 = (\Sigma, N_2, P_2, S_2)$ für $L_2$. Ob die beiden Alphabete die gleichen sind, also beide $\Sigma$, oder zwei verschiedene, also $\Sigma_1, \Sigma_2$, ist nicht entscheidend, da wir im letzteren Fall $L_1$ und $L_2$ als Sprachen über dem Alphabet $\Sigma := \Sigma_1 \cup \Sigma_2$ betrachten können. Wir führen nun wiederum ein neues Startsymbol $S \not \in N_1 \cup n_2$ ein und fügen die Regel

S \rightarrow S_1 S_2

hinzu. Es sollte nun klar sein, dass wir aus $S$ genau die Wörter der Form $\alpha \beta$ mit $S_1 \Rightarrow^* \alpha$ und $S_2 \Rightarrow^* \beta$ ableiten können, also genau die in $L_1 \cup L_2$. Leider ist die Regel $S \rightarrow 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{align*} \begin{array}{l|l} \textnormal{Regel in $G_1$}& \textnormal{wird zu} \\ \hline X \rightarrow aY&X \rightarrow aY X \rightarrow a&X \rightarrow aS_2 \\ X \rightarrow Y&X \rightarrow Y \\ X \rightarrow \epsilon&Y \rightarrow S_2 \ . \end{array} \end{align*}

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$.A$\square$

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 \Sigma^*$. Die Sprache $L^n$ ist die Menge

\begin{align*} L^n := \{ \alpha_1 \alpha_2 \dots \alpha_n \ | \ \alpha_i \in L \ \forall 1 \leq i \leq n \} \ . \end{align*}

Insbesondere ist $L^1 = L$ und $L^0 = \{\epsilon\}$. Die Menge $L^*$ ist nun

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

also die Sprache der Wörter der Form $\alpha_1 \alpha_2 \dots \alpha_n$, wobei $n$ beliebig und jedes $\alpha_i \in L$ ist.

Lemma 5.1.13 Sei $L$ eine reguläre Sprache. Dann ist $L^*$ auch regulär.

Beweis. Sei $G = (\Sigma, N, P, S)$ eine reguläre Grammatik für $L$. Wir könnten ein neues Startsymbol $S'$ einführen und

\begin{align*} S' &\rightarrow \epsilon \\ S'&\rightarrow SS' \end{align*}

als zwei neue Regeln einführen. Natürlich geht das nicht, denn $S' \rightarrow SS'$ ist nicht erlaubt in regulären Grammatiken. Ähnlich wie im vorherigen Beweis fangen wir das Ende einer $G$ -Ableitung ab:

\begin{align*} \begin{array}{l|l} \textnormal{Regel in $G$}&\textnormal{wird zu} \\ \hline X \rightarrow aY&X \rightarrow aY \\ X \rightarrow a&X \rightarrow aS \\ X \rightarrow Y&X \rightarrow Y \\ X \rightarrow \epsilon& Y \rightarrow S \ . \end{array} \end{align*}

Um überhaupt eine Ableitung beenden zu können, fügen wir $S \rightarrow \epsilon$ noch als Regel hinzu.A$\square$

Ü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 \Sigma^*$ eine reguläre Sprache und $c \not \in \Sigma$ ein neues Terminalsymbol. Die Sprache aller nichtleeren Folgen von $L$ -Wörten, die durch $c$ separiert sind, also formal

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

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 = $\Sigma, 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 $cS$ 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 \rightarrow \epsilon$ fügen wir $Y \rightarrow cS$ hinzu. Für jede $G$-Produktion der Form $Y \rightarrow a$ fügen wir $Y \rightarrow acS$ hinzu. Die neue Grammatik $G'$ ist eine erweitert reguläre Grammatik, da Regeln wie $Y \rightarrow acS$ 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.A\(\square$

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.