Figure 3.16. The complete automaton is assembled from such individual parts.
Suppose now that w ∈ L(G) so that (3.4) is satisfied. In the nfa there is, by
construction, a path from V 0 to V i labeled v 1 , a path from V i to V j labeled v 2 , and
so on, so that clearly
Vf ∈δ* (V 0 ,w),
and w is accepted by M.
Conversely, assume that w is accepted by M. Because of the way in which M
was constructed, to accept w the automaton has to pass through a sequence of
states V 0 ,V i ,…to V f , using paths labeled v 1 ,v 2 ,…. Therefore, w must have the
form
w= v 1 v 2 … v k v l
and the derivation
is possible. Hence w is in L (G), and the theorem is proved.
Example 3.15
Construct a finite automaton that accepts the language generated by the grammar
V 0 aV 1 ,
V 1 abV 0 |b,
where V 0 is the start variable. We start the transition graph with vertices V 0 , V 1 ,
and V f . The first production rule creates an edge labeled a between V 0 and V 1 .
For the second rule, we need to introduce an additional vertex so that there is a
path labeled ab between V1 and V 0 . Finally, we need to add an edge labeled b
between V 1 and V f , giving the automaton shown in Figure 3.17. The language
generated by the grammar and accepted by the automaton is the regular language
L ((aab) * ab.