Lineare Sprache

Klasse formaler Sprachen in der theoretischen Informatik

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

Bearbeiten

Eine lineare Grammatik   ist eine kontextfreie Grammatik, deren Produktionsregeln von einer der folgenden Formen sind:

 

Wobei

 

Einseitig lineare Grammatiken

Bearbeiten

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

 

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

Trifft man die Festlegung, dass alle Produktionsregeln einer der Formen

 

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

Bearbeiten

Es sei   eine Grammatik mit:

 
 
 

Offenbar werden mit diesen Regeln alle Palindrome über   produziert:   wird in der Literatur oft mit   bezeichnet.

Ähnlich gibt es Regeln für die Sprache  .

Eigenschaften

Bearbeiten

Äquivalenz zu Kellerautomaten

Bearbeiten
  • 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:   und  

Beziehung zu regulären und kontextfreien Sprachen

Bearbeiten

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:

 

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

Bearbeiten

Die Klasse der linearen Sprachen ist abgeschlossen unter der

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  : So ist die Sprache   kontextfrei, aber nicht linear. Beweisen lässt sich das mit einem speziellen Pumping-Lemma (= Pumplemma) für lineare Sprachen.

Chomsky-Hierarchie der formalen Sprachen

Bearbeiten

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

  • DLIN   DCFL   CFL   GCSL   CSL
  • REG   DLIN   LIN   METALIN   ULTRALIN   CFL

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

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • 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).
Bearbeiten