productions of the form V 0 → v 1 V i ,V i → v 2 V j ,…or V n → v l ,…. If w is a string in
L (G), then because of the form of the productions
The automaton to be constructed will reproduce the derivation by consuming
each of these v’s in turn. The initial state of the automaton will be labeled V 0 ,
and for each variable V i there will be a nonfinal state labeled V i . For each
production
Vi → a 1 a 2
… a m V j ,
Figure3.16
the automaton will have transitions to connect Vi and Vj that is,δ will be defined
so that
δ * (V i ,a 1 a 2
… a m ) = V j .
For each production
V i a 1 a 2
… a m ,
the corresponding transition of the automaton will be
δ* (V i ,a 1 a 2 …a m ) = V f ,
where V f is a final state. The intermediate states that are needed to do this are of
no concern and can be given arbitrary labels. The general scheme is shown in
L (G), then because of the form of the productions
The automaton to be constructed will reproduce the derivation by consuming
each of these v’s in turn. The initial state of the automaton will be labeled V 0 ,
and for each variable V i there will be a nonfinal state labeled V i . For each
production
Vi → a 1 a 2
… a m V j ,
Figure3.16
the automaton will have transitions to connect Vi and Vj that is,δ will be defined
so that
δ * (V i ,a 1 a 2
… a m ) = V j .
For each production
V i a 1 a 2
… a m ,
the corresponding transition of the automaton will be
δ* (V i ,a 1 a 2 …a m ) = V f ,
where V f is a final state. The intermediate states that are needed to do this are of
no concern and can be given arbitrary labels. The general scheme is shown in