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:

$\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

• Lineare Grammatiken – Definition und Eigenschaften von Gerriet Backer und Marita Scheiwe, TU Braunschweig
• Automaten und Formale Sprachen von Berndt Farwer, Uni Hamburg (pdf; 643 kB)