View source for Grammar, regular

<!--
g0448401.png
$#A+1 = 27 n = 0
$#C+1 = 27 : ~/encyclopedia/old_files/data/G044/G.0404840 Grammar, regular,
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}}

''finite-state grammar, automatic grammar, left- (right-) linear grammar''

A context-free grammar (cf. [[Grammar, context-free|Grammar, context-free]]) each rule of which has the form  $  A \rightarrow aB $
or  $  A \rightarrow a $, 
where  $  A $
and  $  B $
are non-terminal symbols and  $  a $
is one of the terminal symbols. (Rules of the form  $  A \rightarrow \Lambda $, 
where  $  \Lambda $
is the empty string, are also sometimes allowed; the class of languages generated is then extended only at the expense of the languages obtained by adding the string  $  \Lambda $
to the previous languages.) For each regular grammar it is possible to construct a finite automaton (cf. [[Automaton, finite|Automaton, finite]]) equivalent to it. The class of languages generated by regular grammars (regular or automatic languages) coincides with the class of regular sets if rules with an empty right-hand side are allowed. The regular languages form a proper subclass of the class of linear languages (cf. [[Grammar, linear|Grammar, linear]]). Thus, the linear language  $  \{ {a  ^ {n} b  ^ {n} } : {n = 1, 2 ,\dots } \} $
is not regular. The class of regular languages is closed under union, intersection, concatenation, substitution, and truncated iteration (and, in the presence of rules with an empty right-hand side, also with respect to iteration). The intersection of a context-free language with a regular language is again a context-free language.

A regular grammar is usually illustrated by a transition diagram — an oriented multi-graph whose vertices are non-terminal symbols, and a vertex  $  A $
is connected to a vertex  $  B $
by means of an arc, marked with the (terminal) symbol  $  a $, 
if  $  A \rightarrow aB $
is a rule of the grammar; in addition, the transition diagram contains one more terminal vertex, connected with a non-terminal symbol  $  A $
by means of an arc marked by the symbol  $  a $
if  $  A \rightarrow a $
is a rule of the regular grammar. (If there are rules of the form  $  A \rightarrow \Lambda $, 
each symbol  $  A $
governed by this rule is also considered to be a terminal vertex.)

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044840a.gif" />

Figure: g044840a

A string in the basic vocabulary is derivable in the grammar from a non-terminal symbol  $  A $
if and only if it is  "written down"  in some path in the diagram going from  $  A $
to the terminal vertex. The figure represents a transition diagram of a regular grammar with the rules  $  I \rightarrow aI $, 
$  I \rightarrow aB $, 
$  B \rightarrow bB $, 
$  B \rightarrow b $(
$  I $
is the initial symbol,  $  K $
is the terminal vertex), which generates the language  $  \{ {a  ^ {n} b  ^ {m} } : {n, m = 1, 2 ,\dots } \} $.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.V. Gladkii,   "Formal grammars and languages" , Moscow  (1973)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  Ya.M. Barzdin',   "Finite automata. Behaviour and synthesis" , North-Holland  (1973)</TD></TR></table>

====Comments====
Cf. also [[Formal languages and automata|Formal languages and automata]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Ginsburg,   "Algebraic theory of automata" , Acad. Press  (1968)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Hartmanis,   R.E. Stearns,   "Algebraic structure theory of sequential machines" , Prentice-Hall  (1966)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.E. Hopcroft,   J.D. Ulman,   "Introduction to automata theory, languages and computation" , Addison-Wesley  (1979)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  S. Ginsburg,   "The mathematical theory of context-free languages" , McGraw-Hill  (1966)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Salomaa,   "Formal languages" , Acad. Press  (1975)</TD></TR></table>