An Introduction to Formal Languages and Automata, 7th Edition

3.3 REGULAR GRAMMARS

A third way of describing regular languages is by means of certain grammars. Grammars are often an alternative way of specifying languages. Whenever we define a language family through an automaton or in some other way, we are interested in knowing what kind of grammar we can associate with the family. First, we look at grammars that generate regular languages.

Right- and Left-Linear Grammars

DEFINITION 3.3

A grammar G = (V, T, S, P) is said to be right-linear if all productions are of the form

$$\begin{array}{l}A\to xB,\hfill \\ A\to x,\hfill \end{array}$$

where A, B ∈ V, and x ∈ T^*. A grammar is said to be left-linear if all productions are of the form

$$A\to Bx,$$

or

$$A\to x.$$

A regular grammar is one that is either right-linear or left-linear.

Note that in a regular grammar, at ...