Lineare Sprache


Lineare Sprache

Die Linearen Sprachen (engl. linear languages, LIN) sind ein Fachbegriff aus der Theoretischen Informatik. So sind sie hier speziell eine Klasse formaler Sprachen und stellen dabei eine echte Teilmenge 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.

Inhaltsverzeichnis

Definition

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 Literatur hat sich die Abkürzung LIN durchgesetzt.

Beispiele

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

N  :=   { S }
Σ := {a,b,c,...,z}
P  :=   { S \rightarrowε, S \rightarrow a, S \rightarrow b, ..., S \rightarrow z,
         S \rightarrow aSa, S \rightarrow bSb, S \rightarrow cSc, ..., S\rightarrow zSz }

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

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

Charakterisierungen

  • Die Klasse der linearen Sprachen entspricht der Klasse der von nichtdeterministischen einfach umkehrenden Kellerautomaten (engl. one turn pda's) akzeptierten Sprachen. Ein Kellerautomat heißt einfach umkehrend, wenn er in allen seinen Berechnungen, nachdem er einmal im Keller gelesen hat, nicht mehr in den Keller 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 Grammatiken, die nur rechts- und links-reguläre 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}

Eigenschaften

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 \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.

Weitergehende Eigenschaften

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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,… …   Deutsch Wikipedia

  • Sprache: Einige allgemeine Eigenschaften —   Das Problem der »Ursprache« der Menschheit ist lange Gegenstand von Spekulationen und wissenschaftlichen Untersuchungen gewesen. Insbesondere wurde wiederholt versucht, von kindlichem Spracherwerb Rückschlüsse auf die Entstehung der… …   Universal-Lexikon

  • Lineare Approximation — Die Differential bzw. Differenzialrechnung ist ein Gebiet der Mathematik und ein wesentlicher Bestandteil der Analysis. Sie ist eng verwandt mit der Integralrechnung, mit der sie unter der Bezeichnung Infinitesimalrechnung zusammengefasst wird.… …   Deutsch Wikipedia

  • Lineare Photophosphorylierung — Photosynthese oder Fotosynthese (griechisch φῶς phōs, Licht; σύνθεσις sýnthesis, Zusammensetzung) ist ein biochemischer Vorgang, den Pflanzen, verschiedene Algengruppen und Bakteriengruppen betreiben. Mit Hilfe von lichtabsorbierenden Farbstoffen …   Deutsch Wikipedia

  • Kontextfrei — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: OMA Verständlichkeit bei den Beispielen ausbauen Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst. Als Kontextfreie Sprache ( …   Deutsch Wikipedia

  • Keller Automat — Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der Theoretischen Informatik. Es handelt sich also um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von …   Deutsch Wikipedia

  • Kellermaschine — Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der Theoretischen Informatik. Es handelt sich also um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von …   Deutsch Wikipedia

  • NKA — Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der Theoretischen Informatik. Es handelt sich also um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von …   Deutsch Wikipedia

  • Push-Down-Automat — Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der Theoretischen Informatik. Es handelt sich also um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von …   Deutsch Wikipedia

  • Stackmaschine — Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der Theoretischen Informatik. Es handelt sich also um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von …   Deutsch Wikipedia