Converting an FSA to a Regular Grammar

We will let each state in the NFA correspond to a non-terminal in the grammar. Each symbol used on the transitions corresponds to a terminal symbol.

Let $S_i$ denote the non-terminal corresponding to state $i$ of the NFA. Then

1. The start symbol of the grammar is $S_0$, the non-terminal corresponding to the start state of the NFA

2. For each transition from state $i$ to state $j$ on some symbol `a', create a production rule of the form: $S_i\; \rightarrow\; {\bf a}S_j$

3. For each state $i$ of the NFA which is a finish state, create a production rule of the form: $S_i\; \rightarrow\; \varepsilon$
   

Note that $\varepsilon$-transitions between states would generate production rules of the form $S_i\; \rightarrow\; S_j$, which says that ``wherever we see $S_i$ we can replace it with $S_j$'' - another indication that $\varepsilon$-transitions denote equivalence.

This process will work equally well with a DFA, and can be applied in reverse to a regular grammar to produce the corresponding NFA.

$$\begin{array}{rcccl} Regular\; Expression & \longleftrightar... ...; DFA & \longleftrightarrow & Regular\; Grammar \\ \end{array}$$