Lineare Grammatik

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Die Artikel Lineare Sprache und Lineare Grammatik überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zusammenzuführen (→ Anleitung). Beteilige dich dazu an der betreffenden Redundanzdiskussion. Bitte entferne diesen Baustein erst nach vollständiger Abarbeitung der Redundanz und vergiss nicht, den betreffenden Eintrag auf der Redundanzdiskussionsseite mit {{Erledigt|1=~~~~}} zu markieren. Nichtich 14:20, 19. Apr. 2011 (CEST)

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[Bearbeiten]

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


    \begin{matrix}
        A \rightarrow & w_1 B w_2 \\
        A \rightarrow & w 
    \end{matrix}

Wobei

 A, B \in N; w, w_1,w_2 \in \Sigma^*

Erzeugte Sprachen[Bearbeiten]

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:


    \begin{matrix}
         S \rightarrow & aSa \\
         S \rightarrow & bSb \\
         S \rightarrow & c
    \end{matrix}

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[Bearbeiten]

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


    \begin{matrix}
         A \rightarrow & w_1 B \\
         A \rightarrow & w \\
    \end{matrix}

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

Trifft man die Festlegung, dass alle Produktionen einer der Formen


    \begin{matrix}
         A \rightarrow & B w_1  \\
         A \rightarrow & w \\
    \end{matrix}

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[Bearbeiten]