language accepted by the graph.
Figure 3.8
The graph of any nondeterministic finite accepter can be considered a
generalized transition graph if the edge labels are interpreted properly. An edge
labeled with a single symbol a is interpreted as an edge labeled with the
expression a, while an edge labeled with multiple symbols a, b,…is interpreted
as an edge labeled with the expression a + b + …. From this observation, it
follows that for every regular language, there exists a generalized transition
graph that accepts it. Conversely, every language accepted by a generalized
transition graph is regular. Since the label of every walk in a generalized
transition graph is a regular expression, this appears to be an immediate
consequence of Theorem 3.1. However, there are some subtleties in the
argument; we will not pursue them here, but refer the reader instead to Exercise
22, Section 4.3, for details.
Equivalence for generalized transition graphs is defined in terms of the
language accepted and the purpose of the next bit of discussion is to produce a
sequence of increasingly simple GTGs. In this, we will find it convenient to
work with complete GTGs. A complete GTG is a graph in which all edges are
present. If a GTG, after conversion from an nfa, has some edges missing, we put
them in and label them with Ø. A complete GTG with |V| vertices has exactly
|V| 2 edges.
Example 3.9
The GTG in Figure 3.9(a) is not complete. Figure 3.9(b) shows how it is
completed.
Figure 3.9