imported>Zooloo: Lemma lautet "Lineare Sprache"; der wichtige spezialfall deterministisch-lineare sprache sollte behandelt werden, aber nicht (und schon gar nicht kommentarlos) den platz des lemmas einnehmen. Ggf. separaten artikel anlegen.

2024-04-16T16:21:50Z

Lemma lautet "Lineare Sprache"; der wichtige spezialfall deterministisch-lineare sprache sollte behandelt werden, aber nicht (und schon gar nicht kommentarlos) den platz des lemmas einnehmen. Ggf. separaten artikel anlegen.

Neue Seite

Die '''Linearen Sprachen''' ([[Englische Sprache|englisch]] ''linear languages'', LIN) sind ein Fachbegriff aus der [[Theoretische Informatik|Theoretischen Informatik]]. So sind sie hier speziell eine Klasse [[Formale Sprache|formaler Sprachen]] und stellen dabei eine echte [[Klasse (Mengenlehre)|Teilklasse]] der '''Typ-2'''-Sprachen der [[Chomsky-Hierarchie]] dar. Gleichzeitig enthalten sie die [[reguläre Sprache|regulären Sprachen]] als echte Teilmenge.

Die Bedeutung der linearen [[Sprache]]n liegt in der Hauptsache darin, dass sie ein Beispiel für eine einfach zu verstehende [[Klasse (Mengenlehre)|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 [[Formale Sprache|formalen Sprachen]] in der [[Theoretische Informatik|theoretischen Informatik]]. Eine lineare Grammatik ist ein Spezialfall einer [[Kontextfreie Grammatik|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 [[Formale Grammatik|Grammatik]] <math>G = \left(N,\Sigma,P,S\right)</math> ist eine [[kontextfreie Grammatik]], deren [[Produktionsregel]]n von einer der folgenden Formen sind:

: <math>
\begin{matrix}
A \rightarrow & w_1 B w_2 \\
B \rightarrow & w
\end{matrix}
</math>

Wobei

: <math> A, B \in N; w, w_1,w_2 \in \Sigma^* </math>

== 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

: <math>
\begin{matrix}
A \rightarrow & w_1 B \\
A \rightarrow & w \\
\end{matrix}
</math>

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

Trifft man die Festlegung, dass alle Produktionsregeln einer der Formen

: <math>
\begin{matrix}
A \rightarrow & B w_1 \\
A \rightarrow & w \\
\end{matrix}
</math>

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äre Grammatik|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 [[Grammatik]]en nach der eingangs getroffenen Definition dann ganz, was verwirren kann. Die linearen [[Sprache]]n haben praktisch viel weniger Bedeutung als die [[Kontextfreie Sprache|kontextfreien Sprachen]] (Typ 2) und die [[Reguläre Sprache|regulären Sprachen]] (Typ 3) und besitzen auch keine „Hausnummer“ in der Hierarchie.

== Beispiele ==
Es sei <math>G = \left( N, \Sigma, P, S \right)</math> eine [[Formale Grammatik|Grammatik]] mit:
:<math>N := \{ S \}</math>
:<math>\Sigma := \{a,b,c,\ldots,z\}</math>
:<math>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 \}</math>
Offenbar werden mit diesen Regeln alle [[Palindrom (Theoretische Informatik)|Palindrome]] über <math>\{a,b,\ldots,z\}</math> produziert: <math>L(G)</math> wird in der Literatur oft mit <math>\mathbf{pal}</math> bezeichnet.

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

== Eigenschaften ==

=== Äquivalenz zu Kellerautomaten ===
* Die Klasse der linearen [[Sprache]]n entspricht der Klasse der von [[Nichtdeterminismus|nichtdeterministischen]] ''einfach umkehrenden [[Kellerautomat]]en'' (englisch ''one turn NPDAs'') [[Akzeptieren (Automaten- und Komplexitätstheorie)|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 [[Determinismus (Algorithmus)|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 Grammatik|formale Grammatiken]], die nur rechts- und links-lineare Regeln enthalten. Wenn nicht beide Typen von Regeln auftauchen, ist die so definierte Sprache bereits [[Reguläre Sprache|regulär]].

* Für die hier vorgestellten Beispielsprachen gilt: <math>\mathbf{count}\in \mathbf{DLIN}</math> und <math>\mathbf{pal} \in \mathbf{LIN}\setminus\mathbf{DLIN}</math>

=== Beziehung zu regulären und kontextfreien Sprachen ===
In der [[Chomsky-Hierarchie]] stehen die linearen [[Sprache]]n zwischen den [[Reguläre Sprache|regulären Sprachen]] und den [[Kontextfreie Sprache|kontextfreien Sprachen]].

Die [[Grammatik]] mit den folgenden Produktionsregeln ist linear, aber nicht regulär:

: <math>
\begin{matrix}
S \rightarrow & aSa \\
S \rightarrow & bSb \\
S \rightarrow & c
\end{matrix}
</math>

Sie erzeugt die Menge der beliebig langen [[Palindrom]]e der Form ''aca'', ''bcb'', ''aabcbaa'', ''abbacabba'' usw., von der gezeigt werden kann, dass sie, im Gegensatz zu einer regulären Sprache, von keinem [[Endlicher Automat|endlichen Automaten]] erkannt werden kann.

=== Mengenoperationen ===

Die [[Klasse (Mengenlehre)|Klasse]] der linearen Sprachen ist abgeschlossen unter der
* [[Vereinigung (Mengenlehre)|Vereinigung]]
* [[Wort (Theoretische Informatik)|Wortumkehrung (Spiegelung)]]
* [[Homomorphismus|Anwendung von Homomorphismen]]
* [[Inverser Homomorphismus|Anwendung von inversen Homomorphismen]]
* Durchschnittbildung mit [[reguläre Sprache|regulären Sprachen]].

Sie ist ''nicht'' abgeschlossen unter
* [[Komplement (Mengenlehre)|Komplement]]
* [[Schnittmenge|Schnitt]]
* Verkettung ([[Konkatenation (Formale Sprache)|Konkatenation]])

Jede [[reguläre Sprache]] ist auch linear, da jede [[reguläre Grammatik]] auch eine lineare Grammatik ist. Es existieren [[kontextfreie Sprache]]n, die nicht linear sind. Ein einfaches Beispiel dafür liefert die oben definierte Sprache <math>\mathbf{pal}</math>: So ist die Sprache <math>L':= \{uv | u\in \mathbf{pal}, v\in \mathbf{pal}\}</math> kontextfrei, aber nicht linear. Beweisen lässt sich das mit einem speziellen [[Pumping-Lemma]] (= Pumplemma) für lineare Sprachen.

== Chomsky-Hierarchie der formalen Sprachen ==
Für die [[Klasse (Mengenlehre)|Klassen]] der formalen Sprachen nach der [[Chomsky-Hierarchie]] sind die Beziehungen der Teilklassen wie folgt:
* '''DLIN''' <math>\subsetneq</math> [[deterministisch kontextfreie Sprache|DCFL]] <math>\subsetneq</math> [[kontextfreie Sprache|CFL]] <math>\subsetneq</math> [[wachsend kontextsensitive Sprache|GCSL]] <math>\subsetneq</math> [[Kontextsensitive Sprache|CSL]]
* [[Reguläre Sprache|REG]] <math>\subsetneq</math> '''DLIN''' <math>\subsetneq</math> '''LIN''' <math>\subsetneq</math> [[METALIN]] <math>\subsetneq</math> [[ULTRALIN]] <math>\subsetneq</math> [[kontextfreie Sprache|CFL]]
Die Klassen LIN der linearen Sprachen und DLIN der deterministisch-linearen Sprachen sind 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 Ullman|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 ==

* [https://www2.informatik.uni-hamburg.de/TGI/lehre/vl/SS02/F2/f2slidesK.pdf.gz Automaten und Formale Sprachen] von Berndt Farwer, Universität Hamburg (PDF; 643 kB; [[Gzip|GZIP]])

[[Kategorie:Theorie formaler Sprachen]]

Lineare Sprache - Versionsgeschichte

imported>Zooloo: Lemma lautet "Lineare Sprache"; der wichtige spezialfall deterministisch-lineare sprache sollte behandelt werden, aber nicht (und schon gar nicht kommentarlos) den platz des lemmas einnehmen. Ggf. separaten artikel anlegen.