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.

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

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

Sie ist nicht abgeschlossen unter

• Komplement
• Schnitt
• Verkettung (Konkatenation)

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

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

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