Lineare Sprache

Die Linearen Sprachen (englisch linear languages, LIN) sind ein Fachbegriff aus der Theoretischen Informatik. So sind sie hier speziell eine Klasse formaler Sprachen und stellen dabei eine echte Teilklasse der Typ-2-Sprachen der Chomsky-Hierarchie dar. Gleichzeitig enthalten sie die regulären Sprachen als echte Teilmenge.

Die Bedeutung der linearen Sprachen liegt in der Hauptsache darin, dass sie ein Beispiel für eine einfach zu verstehende Klasse formaler Sprachen darstellen.

Eine formale Sprache ist genau dann linear, wenn eine lineare Grammatik existiert, die diese Sprache erzeugt. Eine kontextfreie Grammatik heißt lineare Grammatik, wenn auf der rechten Seite einer jeden Regel maximal ein Nichtterminal vorkommt. In der Fachliteratur hat sich die Abkürzung LIN durchgesetzt.

Lineare Grammatik ist ein Begriff aus der Theorie der formalen Sprachen in der theoretischen Informatik. Eine lineare Grammatik ist ein Spezialfall einer kontextfreien Grammatik. Bei ihr gilt gegenüber der kontextfreien Grammatik die zusätzliche Einschränkung, dass auf der rechten Seite jeder Produktionsregel höchstens ein Nichtterminal stehen darf.

Definition

Eine lineare Grammatik $G=\left(N,\Sigma ,P,S\right)$ ist eine kontextfreie Grammatik, deren Produktionsregeln von einer der folgenden Formen sind:

{\begin{matrix}A\rightarrow &w_{1}Bw_{2}\\B\rightarrow &w\end{matrix}}

Wobei

A,B\in N;w,w_{1},w_{2}\in \Sigma ^{*}

Einseitig lineare Grammatiken

Trifft man die zusätzliche Einschränkung, dass auf der rechten Seite jeder Produktionsregel das Nichtterminalsymbol nur am Ende der erzeugten Zeichenkette stehen darf, also einer der Formen

{\begin{matrix}A\rightarrow &w_{1}B\\A\rightarrow &w\\\end{matrix}}

genügen muss, so spricht man von einer rechtslinearen Grammatik.

Trifft man die Festlegung, dass alle Produktionsregeln einer der Formen

{\begin{matrix}A\rightarrow &Bw_{1}\\A\rightarrow &w\\\end{matrix}}

genügen müssen mit also dem Nichtterminal allenfalls am Anfang der rechten Seite, so spricht man von einer linkslinearen Grammatik.

Diese Grammatiken sind den regulären Grammatiken äquivalent, erzeugen also eine eingeschränktere Klasse von Sprachen als die beidseitig linearen Grammatiken.

Manche Quellen benutzen den Begriff lineare Grammatik in abweichender Terminologie synonym zu rechts- oder linkslineare Grammatik, wie eben definiert, und ignorieren die linearen Grammatiken nach der eingangs getroffenen Definition dann ganz, was verwirren kann. Die linearen Sprachen haben praktisch viel weniger Bedeutung als die kontextfreien Sprachen (Typ 2) und die regulären Sprachen (Typ 3) und besitzen auch keine „Hausnummer“ in der Hierarchie.

Beispiele

Es sei $G=\left(N,\Sigma ,P,S\right)$ eine Grammatik mit:

N:=\{S\}

\Sigma :=\{a,b,c,\ldots ,z\}

P:=\{S\rightarrow \epsilon ,S\rightarrow a,S\rightarrow b,\ldots ,S\rightarrow z,S\rightarrow aSa,S\rightarrow bSb,S\rightarrow cSc,\ldots ,S\rightarrow zSz\}

Offenbar werden mit diesen Regeln alle Palindrome über $\{a,b,\ldots ,z\}$ produziert: $L(G)$ wird in der Literatur oft mit $\mathbf {pal}$ bezeichnet.

Ähnlich gibt es Regeln für die Sprache $\mathbf {count} =\{a^{n}b^{n}|n\in \mathbb {N} \}$ .

Eigenschaften

Äquivalenz zu Kellerautomaten

Die Klasse der linearen Sprachen entspricht der Klasse der von nichtdeterministischen einfach umkehrenden Kellerautomaten (englisch one turn NPDAs) akzeptierten Sprachen. Ein Kellerautomat heißt einfach umkehrend, wenn er in allen seinen Berechnungen, nachdem er einmal im Kellerspeicher gelesen hat, nicht mehr in den Kellerspeicher schreibt. Die von deterministischen einfach umkehrenden Kellerautomaten akzeptierten Sprachen werden als deterministisch-lineare Sprachen bezeichnet, in der Literatur meist mit DLIN abgekürzt.
Für alle linearen Sprachen gibt es formale Grammatiken, die nur rechts- und links-lineare Regeln enthalten. Wenn nicht beide Typen von Regeln auftauchen, ist die so definierte Sprache bereits regulär.

Für die hier vorgestellten Beispielsprachen gilt: $\mathbf {count} \in \mathbf {DLIN}$ und $\mathbf {pal} \in \mathbf {LIN} \setminus \mathbf {DLIN}$

Beziehung zu regulären und kontextfreien Sprachen

In der Chomsky-Hierarchie stehen die linearen Sprachen zwischen den regulären Sprachen und den kontextfreien Sprachen.

Die Grammatik mit den folgenden Produktionsregeln ist linear, aber nicht regulär:

{\begin{matrix}S\rightarrow &aSa\\S\rightarrow &bSb\\S\rightarrow &c\end{matrix}}

Sie erzeugt die Menge der beliebig langen Palindrome der Form aca, bcb, aabcbaa, abbacabba usw., von der gezeigt werden kann, dass sie, im Gegensatz zu einer regulären Sprache, von keinem endlichen Automaten erkannt werden kann.

Mengenoperationen

Die Klasse der linearen Sprachen ist abgeschlossen unter der

Vereinigung
Wortumkehrung (Spiegelung)
Anwendung von Homomorphismen
Anwendung von inversen Homomorphismen
Durchschnittbildung mit regulären Sprachen.

Sie ist nicht abgeschlossen unter

Jede reguläre Sprache ist auch linear, da jede reguläre Grammatik auch eine lineare Grammatik ist. Es existieren kontextfreie Sprachen, die nicht linear sind. Ein einfaches Beispiel dafür liefert die oben definierte Sprache $\mathbf {pal}$ : So ist die Sprache $L':=\{uv|u\in \mathbf {pal} ,v\in \mathbf {pal} \}$ kontextfrei, aber nicht linear. Beweisen lässt sich das mit einem speziellen Pumping-Lemma (= Pumplemma) für lineare Sprachen.

Chomsky-Hierarchie der formalen Sprachen

Für die Klassen der formalen Sprachen nach der Chomsky-Hierarchie sind die Beziehungen der Teilklassen wie folgt:

DLIN $\subsetneq$ DCFL $\subsetneq$ CFL $\subsetneq$ GCSL $\subsetneq$ CSL
REG $\subsetneq$ DLIN $\subsetneq$ LIN $\subsetneq$ METALIN $\subsetneq$ ULTRALIN $\subsetneq$ CFL

Die Klassen LIN der linearen Sprachen und DLIN der deterministisch-linearen Sprachen sind fett markiert.

Siehe auch

Literatur

Ludwig Balke, Karl Heinz Böhling. Einführung in die Automatentheorie und Theorie formaler Sprachen. B·I·Wissenschaftsverlag, Mannheim u. a. 1993, ISBN 3-411-16421-2, (Reihe Informatik 90).
S. Ginsburg und E. H. Spanier: Finite-turn pushdown automata. In: SIAM journal on control and optimization 4, 1966, 3, ISSN 0363-0129, S. 429–453.
Seymour Ginsburg: Algebraic and Automata-Theoretic Properties of Formal Languages. Elsevier u. a., Amsterdam u. a. 1975, ISBN 0-7204-2506-9, (Fundamental Studies in Computer Science 2).
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. überarbeitete Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, (i - Informatik).
Michael A. Harrison: Introduction to Formal Language Theory. Addison-Wesley Publishing Co., Reading MA u. a. 1978, ISBN 0-201-02955-3, (Addison-Wesley Series in Computer Science).

Weblinks

Automaten und Formale Sprachen von Berndt Farwer, Universität Hamburg (PDF; 643 kB; GZIP)