Definition

Es hat sich gezeigt, dass zu viele Fragen offen bleiben, wenn man alle möglichen Regeln ohne Einschränkung zulässt (Allgemeine Regelsprachen). Wir lassen daher nur noch ganz wenige Regeln zu und definieren:

Definition: Reguläre Grammatik
Eine Grammatik G = (N,T,P,S) heißt regulär, wenn in allen Produktionen jeweils genau ein Nichtterminal ersetzt werden kann durch genau ein Nichtterminal oder genau ein Terminal oder genau ein Nichtterminal verknüpft mit genau einem Terminal.

Definition: Reguläre Sprache
Eine Sprache L(G) heißt regulär, falls es eine reguläre Grammatik G gibt, die diese Sprache erzeugt.

Für die Einstufung einer Sprache ist also immer die bestmöglich Grammatik entscheidend. Es kann durchaus eine Grammatik gegeben sein, welche vom Typ 0 ist. Die daraus erzeugte Sprache kann jedoch trotzdem vom Typ 3 sein, falls es eine andere Grammatik gibt, die genau die gleiche Sprache erzeugt. Ein Beispiel für einen solchen Fall sind die Beispiele 1 und 2.

linkslineare Sprachen (rechtslineare Sprachen)

Reguläre Grammatiken lassen sich noch präziser einschränken:

Definition: Linkslineare Grammatik
Eine Grammatik G = (N,T,P,S) heißt linkslinear, wenn alle Regeln linkslinear, d. h. von der Form A \rightarrow a, A \rightarrow B oder A \rightarrow Ba. Dabei sollen A, B \in N und a \in T^{*}

Wir lassen also nur Regeln zu, bei denen ein nichtterminales Zeichen in ein anderes oder sich selbst überführt wird und möglicherweise ein Wort aus terminalen Zeichen folgt, oder bei denen ein nichtterminales Zeichen in ein Wort aus terminalen Zeichen überführt wird. Das Wort aus terminalen Zeichen darf leer sein. Der Name linkslinear kommt daher, dass das nichtterminale Zeichen links steht und dass immer nur ein nichtterminales Zeichen auftritt. Damit sind linkslineare Grammatiken spezielle reguläre Grammatiken.

Definition: Linkslineare Sprache
Eine Sprache heißt linkslinear, wenn es eine linkslineare Grammatik gibt, die diese Sprache erzeugt.

Schauen wir unsere bisherigen Beispiele an (Einführung – Beispiele oder Beispiele zu allgemeinen Regelsprachen), so scheint es, als wäre die Regeleinschränkung zu stark ausgefallen, denn keine der bisher verwendeten Grammatiken ist linkslinear.

Allerdings haben wir von einer linkslinearen Sprache nur verlangt, dass es eine linkslineare Grammatik zu ihr gibt. Die Sprache zum Beispiel 4 aus Allgemeine Regelsprachen ist eine linkslineare Sprache, denn sie wird auch von folgender linkslinearen Grammatik erzeugt:

G = (N,T,P,S) mit
N = {S}
T = {0,1}
P = {(S -> S)}
S = S

Beispiele

Im Folgenden soll gezeigt werden, dass es zu den erzeugten Sprachen auch eine linkslineare Grammatik gibt, die diese Sprache erzeugt.

Beispiel 1: Umgangssprachliche Sätze

(siehe Umgangssprachliche Sätze)

Die folgende Grammatik leistet das Gewünschte … und es ist nicht die einzige mit dieser Eigenschaft.

G = (N,T,P,S)
N = {Nominalphrase,Artikel}
T = {Susanne,Katze,Pferd,Heu,Buch,der,die,das,jagt,frisst,liest}
P = {(Satz -> Nominalphrase jagt .),
     (Satz -> Nominalphrase jagt der Katze .),
     (Satz -> Nominalphrase jagt der Pferd .),
     (Satz -> Nominalphrase jagt der Heu .),
     (Satz -> Nominalphrase jagt der Buch .),
     (Satz -> Nominalphrase jagt die Katze .),
     ...
     (Satz -> Nominalphrase frisst .),
     ...
     (Nominalphrase -> Susanne),
     (Nominlaphrase -> Artikel Katze),
     (Nominlaphrase -> Artikel Pferd),
     (Nominlaphrase -> Artikel Heu),
     (Nominlaphrase -> Artikel Buch),
     (Artikel -> der | die | das)}
S = Satz

Wir mussten lediglich einen Teil der Information, die wir durch Regeln in mehreren Stufen versteckt haben, direkt in die Regeln hineinschreiben. Dadurch ist allerdings die Regelmenge deutlich größer geworden.

Beispiel 2: Bezeichner

Ein Bezeichner in einer Programmiersprache soll aus Buchstaben und Ziffern bestehen und mit einem Buchstaben beginnen. Dies wird z. B. durch folgende (kontextfreie) Grammatik gewährleistet:

G = (N,T,P,S)
N = {Bezeichner,Buchstabe,Ziffer}
T = {a,...,z,A,...,Z,0,...,9}
P = {(Bezeichner -> Buchstabe | Bezeichner Buchstabe | Bezeichner Ziffer),
     (Buchstabe -> a ... z | A ... Z),
     (Ziffer -> 0 ... 9)}
S = Bezeichner

Das Beispiel Bezeichner unterscheidet sich vom Beispiel Umgangssprachliche Sätze dadurch, dass die Sprache nicht endlich ist. Die Vorgehensweise zur Umsetzung in eine (regulären) linkslineare Grammatik ist aber die gleiche.

G = (N,T,P,S)
N = {Bezeichner}
T = {a,...,z,A,...,Z,0,...,9}
P = {(Bezeichner -> Bezeichner a | ... | Bezeichner z),
     (Bezeichner -> Bezeichner A | ... | Bezeichner Z),
     (Bezeichner -> Bezeichner 0 | ... | Bezeichner 9),
     (Bezeichner -> a ... z | A ... Z)}
S = Bezeichner

Die Beispiele zeigen, dass es durchaus sinnvoll sein kann, eine Sprache durch eine Grammatik eines anderen Typs zu erzeugen, komplexe Grammatiken lassen sich meist einfacher darstellen. Für eine evtl. spätere Umsetzung (als Automat oder in einem Programm) versucht man jedoch die Grammatik möglichst regulär zu gestalten.

Beispiel 3

G = (N,T,P,S)
N = {S,A}
T = {a,b}
P = {(S -> Sa | Ab),
     (A -> a)}
S = S

In diesem Beispiel wollen wir feststellen, welche Sprache erzeugt wird.

Dazu beginnen wir beim Startzeichen S und versuchen, Regeln anzuwenden. Hier haben wir von S ausgehend immer genau zwei Möglichkeiten, eine Regel anzuwenden. Von A ausgehend haben wir nur eine Regel. Bei den bisherigen Ableitungen ging es uns immer nur darum, aus dem Startzeichen genau ein vorgegebenes Wort der Sprache zu erhalten. Wenn die Regelmenge einfach ist, kann man auch versuchen, sich einen Überblick über alle Worte der Sprache zu verschaffen, indem man bei jedem Wort alle möglichen Regeln anwendet. Dies könnte dann die Grundidee für einen Beweis liefern. Ein damit zu erstellender Ableitungsbaum könnte so aussehen:

Man erkennt (oder beweist durch Induktion), dass die erzeugte Sprache L(G) = \{aba^{n} \mid n \in \mathbb{N}\} ist.

Beispiel 4

G = (N,T,P,S)
N = {S,T}
T = {a,b}
P = {(S -> Sb | Tb),
     (T -> Ta | a)}
S = S

Wir erzeugen wieder die Worte der Sprache durch einen Ableitungsbaum:

Man sieht, dass man mit der Regel (S, Sb) Worte der Form Sb^{m} erzeugen kann. Dann kann man das S durch Tb ersetzen und dieses T durch Ta^{n}. Zuletzt muss das T durch a ersetzt werden. Alle anderen Möglichkeiten führen nicht zu Worten aus V_{T}^{*}. Damit haben aber alle Worte der Sprache L(G) = \{a^{n}b^{m} \mid n,m \in \mathbb{N} \}.