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. Die übliche Abkürzung is DLIN.

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 ${\displaystyle G=\left(N,\Sigma ,P,S\right)}$ ist eine kontextfreie Grammatik, deren Produktionsregeln von einer der folgenden Formen sind:

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

Wobei

${\displaystyle 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

${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle G=\left(N,\Sigma ,P,S\right)}$ eine Grammatik mit:

${\displaystyle N:=\{S\}}$

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

${\displaystyle 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 ${\displaystyle \{a,b,\ldots ,z\}}$ produziert: ${\displaystyle L(G)}$ wird in der Literatur oft mit ${\displaystyle \mathbf {pal} }$ bezeichnet.

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

Eigenschaften

Chomsky-Hierarchie der formalen Sprachen

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

• DLIN ${\displaystyle \subsetneq }$ DCFL ${\displaystyle \subsetneq }$ CFL ${\displaystyle \subsetneq }$ GCSL ${\displaystyle \subsetneq }$ CSL
• REG ${\displaystyle \subsetneq }$ DLIN ${\displaystyle \subsetneq }$ LIN ${\displaystyle \subsetneq }$ METALIN ${\displaystyle \subsetneq }$ ULTRALIN ${\displaystyle \subsetneq }$ CFL

Klasse DLIN der linearen Sprachen ist fett markiert.

Siehe auch

• Formale Sprache
• Sprache
• Formale Grammatik
• Grammatik
• Chomsky-Hierarchie
• Reguläre Sprache
• Kontextfreie Sprache
• Kellerspeicher
• Automat (Informatik)

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)