In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right-hand side of each of its productions.

A linear language is a language generated by some linear grammar.

Example

An example of a linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules

S → aSb

S → ε

It generates the language ${\displaystyle \{a^{i}b^{i}\mid i\geq 0\}}$.

Relationship with regular grammars

Two special types of linear grammars are the following:

• the left-linear or left-regular grammars, in which all rules are of the form A → αw where α is either empty or a single nonterminal and w is a string of terminals;
• the right-linear or right-regular grammars, in which all rules are of the form A → wα where w is a string of terminals and α is either empty or a single nonterminal.

Each of these can describe exactly the regular languages. A regular grammar is a grammar that is left-linear or right-linear.

Note that having a mix of left-linear and right-linear rules does not impose any reduction in the expressive power of linear grammars. Indeed, by adding new nonterminals as abbreviations, any linear grammar can be turned into an equivalent one where some of the rules are left-linear and some are right-linear. For instance, the rules of the grammar G above generating ${\displaystyle \{a^{i}b^{i}\mid i\geq 0\}}$ can be replaced with

S → aA

A → Sb

S → ε

which generates the same language. It is the requirement that all rules be left-linear, or all rules be right-linear, that characterizes regular languages and thus leads to a strict decrease in the expressive power of linear grammars.

Expressive power, nondeterminism, and complexity

All regular languages are linear; conversely, ${\displaystyle \{a^{i}b^{i}\mid i\geq 0\}}$ is an example of a non-regular linear language. All linear languages are context-free; conversely, an example of a context-free, non-linear language is the Dyck language of well-balanced bracket pairs. Hence, the regular languages are a proper subset of the linear languages, which in turn are a proper subset of the context-free languages.

Just as the regularity problem for context-free languages is undecidable, it cannot be decided whether a given context-free language is a linear context-free language.^[1]

While regular languages are deterministic, there exist linear languages that are nondeterministic. For example, the language of even-length palindromes on the alphabet of 0 and 1 has the linear grammar S → 0S0 | 1S1 | ε, but cannot be recognized by any deterministic pushdown automaton.^[2] In particular, the existence of nondeterministic linear languages can be used to derive Ω(n²/log n) lower bounds for the online recognition problem for linear grammars.^[3]

One-turn pushdown automata and ultralinear grammars

A language is linear iff it can be generated by a one-turn pushdown automaton – a pushdown automaton that, once it starts popping, never pushes again. If one instead places a finite bound on the number of turns then one obtains a more general class of languages known as ultralinear, still strictly contained in the context-free languages, and which have a corresponding grammatical characterization.^[4] A grammar is ultralinear if the set of nonterminals can be decomposed as a disjoint union of sets ${\displaystyle N=N_{0}\cup N_{1}\cup \dots \cup N_{k}}$, such that for each nonterminal ${\displaystyle X\in N_{i}}$, each production rule is of the form ${\displaystyle X\to \alpha Y\beta }$ or ${\displaystyle X\to \alpha }$, where ${\displaystyle Y\in N_{i}}$ and ${\displaystyle \alpha ,\beta \in (\Sigma \cup N_{0}\cup \dots \cup N_{i-1})^{*}}$. (Thus linear grammars correspond to the case ${\displaystyle k=0}$.)

Closure properties

References