Linear grammar

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

Definition

A linear grammar is a context-free grammar whose productions are of the following forms:

In which

Generated languages

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

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

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

One-sided linear grammars

Hitting the additional restriction that on the right hand side of each production, the non-terminal symbol may only appear at the end of the string generated, so any of the forms

Must meet, we speak of a right- linear grammar.

Hitting the stipulation that all productions of the forms

Therefore must comply with the non-terminal at best at the beginning of the right side, it is called a left- linear grammar.

These grammars are equivalent to regular grammars, thus producing a more limited set of languages ​​as both sides linear grammars.

Some sources use the term linear grammar in a different terminology synonymous with right -or left- linear grammar, as just defined, and ignore the linear grammars according to the initially adopted definition then all of what can be confusing. The linear languages ​​have practically much less important than the context-free (type 2) and the regular (Type 3) and also do not have a " house number " in the hierarchy.