Suppose now that we have the simple two-state complete GTG shown in
Figure 3.10. By mentally tracing through this GTG you can convince yourself
that the regular expression covers all possible paths and so is the correct regular
expression associated with the graph.
When a GTG has more than two states, we can find an equivalent graph by
removing one state at a time. We will illustrate this with an example before
going to the general method.
Figure 3.10
Example 3.10
Consider the complete GTG in Figure 3.11. To remove q2, we first intoduce
some new edges. We
create an edge from q 1 to q 1 and label it e + af*b,
create an edge from q 1 to q 3 and label it h + af *c,
create an edge from q 3 to q 1 and label it i + df *b,
create an edge from q 3 to q 3 and label it g + df *c.
When this is done, we remove q 2 and all associated edges. This gives the GTG in