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 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:
In which
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:
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
must suffice, one speaks of a right-linear grammar .
One takes the stating that all productions are one of the forms
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 )