Problem Solving in Automata, Languages, and Complexity

1.3 Graph Representations 17

Figure 1.2: A digraph.

In some applications, we would like to assign labels to edges of a digraph.

Such a digraph is called a labeled &graph. In general, we allow more than one

edge from a vertex u to a vertex V, if they have different labels.

There is an interesting way to represent regular expressions by labeled

digraphs with labels from C U {E}. For any regular expression r, its labeled

digraph representation can be obtained as follows:

1. Initially, we start with two special vertices, the initial vertex and the
   fincll vertex, and draw an edge between them with label T (see Figure
   1.3(l)). (In Figure 1.3(l), we draw an arrow with no starting point to
   the initial vertex and use double circles to denote the final vertex.)


2. Repeat the following until every edge has a label that does not contain
   operation symbols +, l , or :
   Replace each edge with label f + g by two edges with labels f and
   g, as shown in Figure 1.3(2).
   Replace each edge with label fg by an additional vertex and two
   edges with labels f and g, as shown in Figure 1.3(3).
   Replace each edge with label f by an additional vertex and three
   edges with labels E, f, and E, as shown in Figure 1.3(4).


3. Delete all edges with label 8.
   For a regular expression lr, let G(r) be its graph representation constructed

as above. Clearly, each edge in G(r) h as a label in C U {E}. Every path

in G(r) is associated with a string which is obtained by concatenating all

symbols labeling the edges in the path. This representation has the following

property:

Theorem 1.23 Let r be a regular expression. A string x belongs to the Zan-

!.Page L(r) i f an d only if there is a path in G(r) from the initial vertex to the

final vertex whose associated string is x.

Proof Let ~1 be the initial vertex and q be the final vertex in G(r). Consider

the following statement: