Linear grammar

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.

A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules

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

Two special types of linear grammars are the following:

Collectively, these two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages.

Another special type of linear grammar is the following:

By inserting new nonterminals, every linear grammar can be brought into this form without affecting the language generated. For instance, the rules of G above can be replaced with

Hence, linear grammars of this special form can generate all linear languages.

All regular languages are linear; conversely, an example of a linear, non-regular language is {aⁿbⁿ}, as explained above. 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.

...
Wikipedia