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 denote the non-terminal corresponding to state
of the NFA. Then
Note that -transitions between states would generate
production rules of the form
, which says
that ``wherever we see
we can replace it with
'' - another
indication that
-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.