Namespaces
Variants
Actions

Difference between revisions of "Grammar, linear"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A context-free grammar (cf. [[Grammar, context-free|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044830/g0448301.png" /> is not linear). See also [[Grammar, regular|Grammar, regular]].
+
<!--
 +
g0448301.png
 +
$#A+1 = 1 n = 0
 +
$#C+1 = 1 : ~/encyclopedia/old_files/data/G044/G.0404830 Grammar, linear
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
A context-free grammar (cf. [[Grammar, context-free|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 $  \{ {a  ^ {n} b  ^ {n} a  ^ {m} b  ^ {m} } : {n, m = 1, 2 ,\dots } \} $
 +
is not linear). See also [[Grammar, regular|Grammar, regular]].

Latest revision as of 19:42, 5 June 2020


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 $ \{ {a ^ {n} b ^ {n} a ^ {m} b ^ {m} } : {n, m = 1, 2 ,\dots } \} $ 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