Namespaces
Variants
Actions

Grammar, linear

From Encyclopedia of Mathematics
Revision as of 17:12, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A context-free grammar (cf. Grammar, context-free) in which the right-hand side of each rule contains at most one occurrence of a non-terminal symbol. The class of languages generated by such grammars (linear languages) is a proper subclass of the class of context-free languages (e.g., the context-free language is not linear). See also Grammar, regular.

How to Cite This Entry:
Grammar, linear. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Grammar,_linear&oldid=47118
This article was adapted from an original article by A.V. Gladkii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article