Wikipedia · einfach zusammengefasst · Stand
Lineare Sprache
... Informatik. So sind sie hier speziell eine Klasse formaler Sprachen und stellen dabei eine echte Teilklasse der Typ-2-Sprachen der Chomsky-Hierarchie dar.
Inhalt5 Abschnitte
Kernidee und Definition
Lineare Sprachen, abgekürzt LIN, sind eine Klasse formaler Sprachen aus der theoretischen Informatik. Sie gehören zur Chomsky-Hierarchie: Sie bilden eine echte Teilklasse der Typ-2-Sprachen, also der kontextfreien Sprachen, und enthalten zugleich die regulären Sprachen als echte Teilmenge. Ihre Bedeutung liegt vor allem darin, dass sie eine relativ einfach zu verstehende Klasse formaler Sprachen darstellen.
Eine formale Sprache ist genau dann linear, wenn es eine lineare Grammatik gibt, die diese Sprache erzeugt. Eine lineare Grammatik ist ein Spezialfall einer kontextfreien Grammatik. Bei ihr darf auf der rechten Seite jeder Produktionsregel höchstens ein Nichtterminal stehen. Nichtterminale sind Hilfssymbole der Grammatik; Terminalsymbole sind die eigentlichen Zeichen der erzeugten Wörter.
Formal ist eine lineare Grammatik G = (N, Σ, P, S) eine kontextfreie Grammatik, deren Produktionsregeln eine der Formen A → w₁Bw₂ oder B → w haben. Dabei gilt A, B ∈ N und w, w₁, w₂ ∈ Σ*.
Rechts- und linkslineare Grammatiken
Bei einseitig linearen Grammatiken wird zusätzlich eingeschränkt, wo das höchstens eine Nichtterminal auf der rechten Seite stehen darf.
Eine rechtslineare Grammatik hat Regeln der Formen A → w₁B oder A → w. Das Nichtterminalsymbol darf also nur am Ende der erzeugten Zeichenkette stehen.
Eine linkslineare Grammatik hat Regeln der Formen A → Bw₁ oder A → w. Das Nichtterminal darf also höchstens am Anfang der rechten Seite stehen.
Rechtslineare und linkslineare Grammatiken sind den regulären Grammatiken äquivalent. Sie erzeugen daher eine eingeschränktere Sprachklasse als beidseitig lineare Grammatiken. Manche Quellen verwenden den Begriff „lineare Grammatik“ abweichend nur für rechts- oder linkslineare Grammatiken; das kann verwirrend sein. Lineare Sprachen haben insgesamt deutlich weniger praktische Bedeutung als kontextfreie Sprachen vom Typ 2 und reguläre Sprachen vom Typ 3 und besitzen keine eigene „Hausnummer“ in der Chomsky-Hierarchie.
Typische Beispiele
Ein wichtiges Beispiel ist die Sprache aller Palindrome über dem Alphabet {a, b, ..., z}. Dazu wird eine Grammatik G = (N, Σ, P, S) angegeben mit N := {S}, Σ := {a,b,c,...,z} und Regeln wie S → ε, S → a, S → b, ..., S → z sowie S → aSa, S → bSb, S → cSc, ..., S → zSz. Diese Regeln erzeugen genau Wörter, die vorwärts und rückwärts gleich gelesen werden können. Die erzeugte Sprache L(G) wird in der Literatur oft mit pal bezeichnet.
Ein weiteres Beispiel ist die Sprache count = {aⁿbⁿ | n ∈ ℕ}. Sie besteht aus Wörtern mit gleich vielen a am Anfang und b danach. Für diese Sprache gibt es ebenfalls entsprechende lineare Regeln.
Automaten und wichtige Eigenschaften
Die Klasse der linearen Sprachen entspricht der Klasse der Sprachen, die von nichtdeterministischen einfach umkehrenden Kellerautomaten akzeptiert werden. Ein Kellerautomat besitzt einen Kellerspeicher, also eine Art Stapel. „Einfach umkehrend“ bedeutet: Nachdem der Automat in einer Berechnung einmal aus dem Kellerspeicher gelesen hat, schreibt er danach nicht mehr in den Kellerspeicher.
Die Sprachen, die von deterministischen einfach umkehrenden Kellerautomaten akzeptiert werden, heißen deterministisch-lineare Sprachen. Sie werden meist mit DLIN abgekürzt.
Für alle linearen Sprachen gibt es formale Grammatiken, die nur rechts- und linkslineare Regeln enthalten. Wenn nicht beide Typen von Regeln vorkommen, ist die dadurch definierte Sprache bereits regulär.
Für die Beispielsprachen gilt: count ∈ DLIN und pal ∈ LIN \ DLIN. Die Sprache count ist also deterministisch-linear, während pal linear, aber nicht deterministisch-linear ist.
Einordnung und Mengenoperationen
In der Chomsky-Hierarchie stehen lineare Sprachen zwischen den regulären Sprachen und den kontextfreien Sprachen. Jede reguläre Sprache ist auch linear, weil jede reguläre Grammatik auch eine lineare Grammatik ist. Es gibt aber kontextfreie Sprachen, die nicht linear sind.
Ein Beispiel für eine lineare, aber nicht reguläre Grammatik hat die Regeln S → aSa, S → bSb und S → c. Sie erzeugt Palindrome der Form aca, bcb, aabcbaa, abbacabba usw. Diese Sprache kann im Gegensatz zu regulären Sprachen von keinem endlichen Automaten erkannt werden.
Die Klasse der linearen Sprachen ist abgeschlossen unter Vereinigung, Wortumkehrung oder Spiegelung, Anwendung von Homomorphismen, Anwendung von inversen Homomorphismen und Durchschnittbildung mit regulären Sprachen. „Abgeschlossen“ bedeutet hier: Wendet man die jeweilige Operation auf lineare Sprachen an, erhält man wieder eine lineare Sprache.
Nicht abgeschlossen ist die Klasse der linearen Sprachen unter Komplement, Schnitt und Verkettung, auch Konkatenation genannt. Ein Beispiel für eine kontextfreie, aber nicht lineare Sprache ist L' := {uv | u ∈ pal, v ∈ pal}. Beweisen lässt sich dies mit einem speziellen Pumping-Lemma, auch Pumplemma, für lineare Sprachen.
Die Beziehungen wichtiger Sprachklassen werden im Artikel unter anderem so angegeben: DLIN ⊊ DCFL ⊊ CFL ⊊ GCSL ⊊ CSL sowie REG ⊊ DLIN ⊊ LIN ⊊ METALIN ⊊ ULTRALIN ⊊ CFL. Dabei steht REG für reguläre Sprachen, LIN für lineare Sprachen, DLIN für deterministisch-lineare Sprachen und CFL für kontextfreie Sprachen.
