Figure 3.12. You can explore the equivalence of the two GTGs by seeing how
regular expressions such as af* c and e* ab are generated.
Figure 3.11
Figure 3.12
For arbitrary GTGs we remove one state at a time until only two states are
left. Then we apply Equation (3.1) to get the final regular expression. This tends
to be a lengthy process, but it is staightforward as the following procedure
shows.
procedure: nfa-to-rex
1. Start with an nfa with states q 0 ,q 1 ,…..,q n , and a single final state, distinct
from its initial state.
2. Convert the nfa into a complete generalized transition graph. Let rij stand for
the label of the edge from q i q j .
3. If the GTG has only two states, with q i as its initial state and q j its final state,
its associated regular expression is
4. If the GTG has three states, with initial state q i , final state q j , and third state
q k , introduce new edges, labeledfor p =i,j, q =i,j. When this is done, remove
vertex q k and its associated edges.
regular expressions such as af* c and e* ab are generated.
Figure 3.11
Figure 3.12
For arbitrary GTGs we remove one state at a time until only two states are
left. Then we apply Equation (3.1) to get the final regular expression. This tends
to be a lengthy process, but it is staightforward as the following procedure
shows.
procedure: nfa-to-rex
1. Start with an nfa with states q 0 ,q 1 ,…..,q n , and a single final state, distinct
from its initial state.
2. Convert the nfa into a complete generalized transition graph. Let rij stand for
the label of the edge from q i q j .
3. If the GTG has only two states, with q i as its initial state and q j its final state,
its associated regular expression is
4. If the GTG has three states, with initial state q i , final state q j , and third state
q k , introduce new edges, labeledfor p =i,j, q =i,j. When this is done, remove
vertex q k and its associated edges.