linear language


A formal grammar G=(Σ,N,P,σ) is said to be linear if each of its productions has the form Ax, where A is a non-terminal, and x is a word over Σ containing no more than one occurrence of a non-terminal. In other words, a production in G has one of the following forms:

  1. 1.

    Aλ (the empty word)

  2. 2.

    Au, where u is a terminal word (over the set of terminal symbols Σ-N), or

  3. 3.

    AuBv, where u,v are terminal words, and B is a non-terminal symbol (in N).

A langauge generated by a linear grammar is called a linear language.

By definition, any linear language is context-free. However, not all context-free languages are linear. A Dyck languageMathworldPlanetmath is an example of a non-linear context-free language.

Furthermore, every regular language is linear, since any production of a regular grammar has one of the above three forms, except v=λ in the last form. The converseMathworldPlanetmath is also not true. For example, the languagePlanetmathPlanetmath {anbnn0} is known to be not regularPlanetmathPlanetmath (apply the pumping lemmaPlanetmathPlanetmath), but it is linear, generated by the following productions σλ, σaσb.

It can be shown that a language is linear iff it can be generated by a 1-turn pushdown automaton (once it starts popping, it never pushes again).

As we have seen above, a regular grammar is a more restricted form of a linear grammar. Various restrictionsPlanetmathPlanetmathPlanetmath may be placed on a linear grammar G:

  • G is right linear if v=λ is the third form above (so a regular grammar is also known as a right linear grammar)

  • G is strong right linear if it is right linear, and there are no productions of the second form

  • G is left linear if u=λ in the third form above

  • G is strong left linear if it is left linear, and there are no productions of the second form

However, it can be shown that all of the restricted types of linear grammars mentioned above are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath, in the sense that a language generated by one restricted type can be generated by all other restricted types.

Remark. Subfamilies of the family of linear languages can be formed by putting restrictions on the linear grammars. In some cases, the subfamily formed properly sits between the family of regular languages and the family of linear languages. Here are some examples: let G=(Σ,N,P,σ) be a linear grammar,

  • G is minimalPlanetmathPlanetmath if N={σ}, and there is exactly one production of the form σa, where aΣ such that a occurs in no other productions. Therefore, if σu is another production of G, then uΣ, and a does not occur in u.

  • G is even if every production having the third form above (AuBv) has the property that |u|=|v| (same length). It can be shown that every regular language can be generated by an even linear grammar, and that the converse is not true.

  • G is deterministicMathworldPlanetmath if every production has the form AaW, where aΣ-N, and W is either the empty word λ, or in N(Σ-N)*. Furthermore, every (A,a)N×(Σ-N) corresponds to at most one production.

References

  • 1 S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York (1966).
  • 2 H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
  • 3 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their RelationMathworldPlanetmath to Automata, Addison-Wesley, (1969).
Title linear language
Canonical name LinearLanguage
Date of creation 2013-03-22 18:55:55
Last modified on 2013-03-22 18:55:55
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 68Q45
Classification msc 68Q42
Synonym left linear
Synonym right linear
Synonym strong left linear
Synonym strong right linear
Related topic MetalinearLanguage
Defines linear grammar
Defines left-linear
Defines right-linear
Defines strong left-linear
Defines strong right-linear
Defines minimal linear grammar
Defines even linear grammar
Defines deterministic linear grammar