Linear grammar

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged with Regular grammar. (Discuss)

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help improve the introduction to meet Wikipedia's layout standards. You can discuss the issue on the talk page.

In computer science, a grammar is linear if all of its productions' right hand sides have at most one variable. As such, linear grammars are more general than regular grammars.

Two special cases of linear grammars are left-linear grammars (also called left regular grammars) and right-linear grammars (also called right regular grammars). The set of regular grammars is the union of all right-linear grammars and left-linear grammars.

A language is produced by a left-linear grammar if and only if it is a regular language. A language is also regular if and only if it is produced by a right-linear grammar. However, grammars that mix right-linear and left-linear productions may produce languages that are not regular.

The equivalence between the languages described by right-linear(left-linear) grammars and regular languages can be shown by constructing a finite automaton which accepts the same language as the right-linear(left-linear) grammar and vice-versa.

[edit] Left-Linear Grammars

In left-linear grammars, also known as left regular grammars, all productions have one of the two forms:

                            A → B t* 
                      or    A → t*

where A and B are any nonterminal symbols, and t* is any string of terminal symbols. That is, the left-hand side must consist of a single variable, and the right-hand side must consist of an optional single variable followed by any number of terminal symbols.

[edit] Right-Linear Grammars

In right-linear grammars, also known as right regular grammars, all productions have one of the two forms:

                            A → t* B 
                      or    A → t*

where A and B are any nonterminal symbols, and t* is any string of terminal symbols. That is, the left-hand side must consist of a single variable, and the right-hand side must consist of any number of terminal symbols optionally followed by a single variable.