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 $G=\left(N,\Sigma ,P,S\right)$ ist eine kontextfreie Grammatik, deren Produktionen von einer der folgenden Formen sind:

$A\rightarrow w_{1}Bw_{2}$ $A\rightarrow w$

mit $A\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 folgende Grammatik mit ist linear, aber nicht regulär:

• S → aSa
• S → bSb
• S → c

Sie erzeugt Palindrome der Form aca, bcb, aabcbaa, abbacabba usw., von denen gezeigt werden kann, dass sie von keinem endlichen Automaten erkannt werden können.

Weblinks

Lineare Grammatiken - Definition und Eigenschaften von Gerriet Backer und Marita Scheiwe, TU Braunschweig