Lineare Grammatik

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.

Inhaltsverzeichnis

Definition

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

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

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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Kontextfreie Grammatik — In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik eine Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminal auf eine beliebig lange Folge von Nichtterminalen und Terminale abgeleitet wird …   Deutsch Wikipedia

  • Kontextfrei — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: OMA Verständlichkeit bei den Beispielen ausbauen Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst. Als Kontextfreie Sprache ( …   Deutsch Wikipedia

  • Auflösbar — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

  • Euklidisch — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

  • Fehlstand — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

  • Integrabel — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

  • Kollinear — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

  • Kopunktal — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

  • Mathematisches Attribut — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”