Regular Grammar

languages

Definition

Regular Grammar

A grammar $G$ is called regular if every production rule is regular.

Examples

Grammar from Finite Automaton

Consider the following finite automaton:

To construct a grammar $G$ from the automaton above, we treat states as non-terminal symbols and output symbols as terminal symbols. Trivially, the start symbol is the start state $q_0$.

$$G=⟨\{q_0,q_1\},\{0,1\},P,q_0⟩$$

Next, we create the set of production rules from the transitions of the automaton:

$$\begin{array}{r}{q}_0\to 0q_0\mid 1q_1\\ q_1\to 0q_1\mid 1q_0\end{array}$$

Given that $q_1$ is the accepting state, we have to allow $G$ to produce a terminal string. Therefore, we add another production rule to $P$:

$$q_1\to \epsilon$$