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.