Regular Grammars

A regular grammar is a grammar where all of the production rules are of one of the following forms:

$$\begin{array}{lrcl} & A & \rightarrow & {\bf a} B \\ or & A & \rightarrow & {\bf a} \\ \end{array}$$

where $A$ and $B$ represent any single non-terminal, and a represents any single terminal, or the empty string.

If a grammar can only derive regular languages, but is not of the above form, then (we claim) it can be converted to this form. In order to justify our assertion that we can represent all regular expressions in this manner, we give an algorithm for converting from an FSA to a regular grammar.