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 = SIm 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 = SatzWir 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 = BezeichnerDas 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 = BezeichnerDie 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.
Eigenschaften linkslinearer Sprachen
Die leere Menge \{ \} ist linkslinear.
Wir wählen P = \{(S \rightarrow S)\} für beliebige Mengen N und T. Diese zulässige Regel führt nie zu einem terminalen Zeichen. Also ist die zugehörige Sprache leer. (vgl. auch Beispiel 4 aus Allgemeine Regelsprachen).
Jede einelementige Sprache \{w\} ist linkslinear.
Wir wählen P = \{(S \rightarrow w)\}.
Jede endliche Sprache {w1,w2,…,wn} ist linkslinear.
Wir wählen P = \{(S \rightarrow w_{1} \mid w_{2} \mid ... \mid w_{n})\}.
Es gibt unendliche, linkslineare Sprachen.
Wir wählen als Beispiel T^{*} und konstruieren dazu folgende Regelmenge: Zu P sollen dazu genau alle Regeln der Formen (S \rightarrow x) und (S \rightarrow Sx) für alle x \in T gehören sowie die Regel (S \rightarrow \epsilon) zur Erzeugung des leeren Wortes. Hierbei und bei den obigen Begründungen ist S \in N das Startsymbol.
Sind L_{1} und L_{2} linkslineare Sprachen, so ist auch die Vereinigung L_{1} \cup L_{2} linkslinear.
Seien L1 = L(G1) mit G1 = (N1,T1, P1, S1) und L2 = L(G2) mit G2 = (N2, T2, P2, S2) gegeben. Durch eventuelles Umbenennen kann man erreichen, dass N1 und T2 disjunkt sind. S sei ein Zeichen, das in ihrer Vereinigung nicht enthalten ist.
Dann erzeugt folgende Grammatik G = (N, T, P, S) die gesuchte Sprache L_{1} \cup L_{2}:
Wenn man aus dem Startzeichen S mit Hilfe der Regel (S, S1) das Startsymbol S1 der Grammatik G1 erzeugt hat, ist es offensichtlich, dass nur noch Worte aus L1 erzeugt werden können und auch genau diese. Entsprechendes gilt für die Worte aus L2.
(Beispiel zur Erläuterung)
Sind L1 und L2 linkslinear, dann ist auch deren Konkatenation (das Produkt, das durch Anhängen eines Wortes aus L2 an ein Wort aus L1 entsteht) linkslinear.
L_{1}L_{2} = \{w \mid w = w_{1}w_{2} \mid w_{1} \in L_{1}, w_{2} \in L_{2} \}Wir nehmen wieder an, dass N1 und N2 disjunkt sind. Sei {N = N_{1} \cup N_{2}} und {V = V_{1} \cup V_{2}}. Das Startzeichen sei S2. In P2 ersetzt man jede Regel der Form (A,w) mit A \in N_{2} und w \in T_{2} durch (A, S1w). Die neue Regelmenge sei P2’. Mit P = P_{1} \cup P_{2} ist man fertig.
Durch die besondere Form der Regeln ist gewährleistet, dass jedes aus S2 abgeleitete Wort aus V* maximal ein nichtterminales Zeichen enthält. Dies ist außerdem das erste Zeichen im Wort. Wenn also in G2 eine abschließende Regel angewendet wird, hat man ein Wort aus L2. Genau diese Regel führt in der abgewandelten Grammatik mit P2’ aber das Startzeichen der Grammatik G1 ein. Aus S1 lassen sich noch genau die Worte aus L1 erzeugen, insgesamt also genau die Worte aus L1L2.
Auch hierzu sei ein Beispiel aus der Analyse von Pascal angegeben. Eine vorzeichenlose Realzahl besteht z. B. aus einer vorzeichenlosen Integer Zahl, einem e und einem Exponenten.
Ist L linkslinear, so ist auch auch L^{*} = \{w^{n} \mid w \in L, n \in \mathbb{N}_{0}\} linkslinear.
Das Wort wn entsteht dabei, wenn w n-mal hintereinander gehängt wird. Die Beweisidee entspricht der des vorhergehenden Beispiels. In P wird zu jeder abschließenden Regel (A, w) die Regel (A, Sw) hinzugenommen. Falls das leere Wort nicht in L ist, muss es noch durch eine eigene Regel (S, \epsilon) erzeugt werden.
Ein Beispiel aus Pascal ist der Prozedur- und Funktionsdeklarationsteil, denn dieser besteht aus beliebig vielen Prozedur- oder Funktionsdeklarationen, kann aber auch leer sein.
Ist L linkslinear, so auch das Komplement T^{*} \setminus L.
Der Beweis ist nicht so einfach wie die vorhergehenden. Wir übergehen ihn deshalb. Für das Studium müssen wir ja noch etwas Platz lassen :)).
Sind L1 und L2 linkslinear, so auch L_{1} \cap L_{2}.
Dies ergibt sich unmittelbar aus den de Morganschen Regeln und den bisher bewiesenen Eigenschaften linkslinearer Sprachen.
Die bisher bewiesenen Eigenschaften linkslinearer Sprachen bilden sehr angenehme Abschlusseigenschaften der Menge der linkslinearen Sprachen. Bei anderen Sprachklassen werden wir davon deutliche Abstriche machen müssen.
Ohne Beweis sei auch angemerkt, dass für linkslineare Grammatiken alle Fragen am Ende des Beitrags Allgemeine Regelsprachen entscheidbar sind.
Beispiel 3
G = (N,T,P,S)
N = {S,A}
T = {a,b}
P = {(S -> Sa | Ab),
(A -> a)}
S = SIn 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 = SWir 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} \}.
