Linear grammar

The articles linear language and linear grammar overlap thematically. Help me to better differentiate or merge the articles (→  instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Not me 14:20, Apr 19, 2011 (CEST)

Linear grammar is a term from the theory of formal languages in theoretical computer science . A linear grammar is a special case of context-free grammar . Compared to the context-free grammar, it has the additional restriction that on the right side of each production rule there may be at most one non-terminal.

definition

A linear grammar is a context-free grammar whose productions are of one of the following forms: ${\displaystyle G=\left(N,\Sigma ,P,S\right)}$

${\displaystyle {\begin{matrix}A\rightarrow &w_{1}Bw_{2}\\B\rightarrow &w\end{matrix}}}$

In which

${\displaystyle A,B\in N;w,w_{1},w_{2}\in \Sigma ^{*}}$

Generated languages

In the Chomsky hierarchy , the linear languages ​​stand between the regular languages and the context-free languages .

The grammar with the following productions is linear but not regular:

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

It generates the set of arbitrarily long palindromes of the form aca , bcb , aabcbaa , abbacabba etc., of which it can be shown that, in contrast to a regular language, it cannot be recognized by any finite automaton .

One-sided linear grammars

If you meet the additional restriction that on the right-hand side of every production, the non-terminal symbol may only appear at the end of the generated character string, i.e. one of the forms

${\displaystyle {\begin{matrix}A\rightarrow &w_{1}B\\A\rightarrow &w\\\end{matrix}}}$

must suffice, one speaks of a right-linear grammar .

One takes the stating that all productions are one of the forms

${\displaystyle {\begin{matrix}A\rightarrow &Bw_{1}\\A\rightarrow &w\\\end{matrix}}}$

with the nonterminal at most at the beginning of the right-hand side, one speaks of a left-linear grammar .

These grammars are equivalent to the regular grammars , so they generate a more restricted set of languages ​​than the bilateral linear grammars.

Some sources use the term linear grammar in different terminology synonymously with right or left linear grammar , as just defined, and then completely ignore the linear grammars according to the definition made at the beginning, which can be confusing. The linear languages ​​are practically much less important than the context-free (type 2) and the regular (type 3) and also have no “house number” in the hierarchy.

Web links

• Automata and formal languages by Berndt Farwer, Uni Hamburg (PDF; 643 kB; GZIP )