Grammar, regular

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

A context-free grammar (cf. Grammar, context-free) each rule of which has the form or , where and are non-terminal symbols and is one of the terminal symbols. (Rules of the form , where 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 to the previous languages.) For each regular grammar it is possible to construct a finite automaton (cf. 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). Thus, the linear language 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 is connected to a vertex by means of an arc, marked with the (terminal) symbol , if is a rule of the grammar; in addition, the transition diagram contains one more terminal vertex, connected with a non-terminal symbol by means of an arc marked by the symbol if is a rule of the regular grammar. (If there are rules of the form , each symbol governed by this rule is also considered to be a terminal vertex.)

Figure: g044840a

A string in the basic vocabulary is derivable in the grammar from a non-terminal symbol if and only if it is "written down" in some path in the diagram going from to the terminal vertex. The figure represents a transition diagram of a regular grammar with the rules , , , ( is the initial symbol, is the terminal vertex), which generates the language .

References

[1]	A.V. Gladkii, "Formal grammars and languages" , Moscow (1973) (In Russian)
[2]	Ya.M. Barzdin', "Finite automata. Behaviour and synthesis" , North-Holland (1973)

Comments

Cf. also Formal languages and automata.

References

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