In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 is linear if it is context-free

Context-free grammar

In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....

 and all of its productions' right hand sides have at most one nonterminal.

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

Example

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

S → aSb

S → ε

It generates the language .

Relationship with regular grammars

Two special types of linear grammars are the following:

• the left-linear or left regular grammars
  Regular grammar
  In theoretical computer science, a regular grammar is a formal grammar that describes a regular language.- Strictly regular grammars :A right regular grammar is a formal grammar such that all the production rules in P are of one of the following forms:# B → a - where B is a non-terminal in N and...
  
  , in which all nonterminals in right hand sides are at the left ends;
• the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.

Collectively, these two special types of linear grammars are known as the regular grammar

Regular grammar

In theoretical computer science, a regular grammar is a formal grammar that describes a regular language.- Strictly regular grammars :A right regular grammar is a formal grammar such that all the production rules in P are of one of the following forms:# B → a - where B is a non-terminal in N and...

s; both can describe exactly the regular language

Regular language

In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....

s.

Another special type of linear grammar is the following:

• linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

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

S → aA

A → Sb

S → ε

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

Expressive power

We have seen that all regular languages are linear; the example gave a linear, non-regular language.
All linear languages are context-free

Context-free language

In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...

 by definition; a simple example of a context-free, non-linear language is the Dyck language

Dyck language

In the theory of formal languages of computer science, mathematics, and linguistics, the Dyck language is the language consisting of balanced strings of parentheses [ and ]. It is important in the parsing of expressions that must have a correctly nested sequence of parentheses, such as arithmetic...

 of well-balanced bracket pairs.

Hence, the regular languages are a proper subset of the linear ones, which in turn are a proper subset of the context-free languages.

Closure properties

If L is a linear language and M is a regular language, then the intersection is again a linear language; in other words, the linear languages are closed under intersection with regular sets. Furthermore, the linear languages are closed under homomorphism and inverse homomorphism. These three closure properties show that the linear languages form a full trio

Cone (formal languages)

In formal language theory, a cone is a set of formal languages that has some desirable closure properties enjoyed by some well-known sets of languages, in particular by the families of regular languages, context-free languages and the recursive languages...

. Full trios in general are language families that enjoy a couple of other desirable mathematical properties.