Lineare Grammatik - LinkFang.de





Lineare Grammatik


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

Eine lineare Grammatik [math]G = \left(N,\Sigma,P,S\right)[/math] ist eine kontextfreie Grammatik, deren Produktionen von einer der folgenden Formen sind:

[math] \begin{matrix} A \rightarrow & w_1 B w_2 \\ A \rightarrow & w \end{matrix} [/math]

Wobei

[math] A, B \in N; w, w_1,w_2 \in \Sigma^* [/math]

Erzeugte Sprachen

In der Chomsky-Hierarchie stehen die linearen Sprachen zwischen den regulären Sprachen und den kontextfreien Sprachen.

Die Grammatik mit den folgenden Produktionen 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 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.

Einseitig lineare Grammatiken

Trifft man die zusätzliche Einschränkung, dass auf der rechten Seite jeder Produktion 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 Produktionen 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ären Grammatiken äquivalent, erzeugen also eine eingeschränktere Menge 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 (Typ 2) und die regulären (Typ 3) und besitzen auch keine „Hausnummer“ in der Hierarchie.

Weblinks


Kategorien: Theorie formaler Sprachen

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Lineare Grammatik (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.