160 ~ Theory ofComputer Science
TABLE 5.8 Comparison Table for Example 5.16
(q. c()
(qi, q4)
(q2' qs)
(q'I' q4)
(Q3' q7)
5.2.7 EQUIVALENCE OF Two REGULAR EXPRESSIONS
Suppose we are interested in testing the equivalence of two regular
expressions, say P and Q. The regular expressions P and Q are equivalent iff
they represent the same set. Also, P and Q are equivalent iff the corresponding
finite automata are equivalent.
To prove the equivalence of P and Q, (i) we prove that the sets P and Q
are the same. (For nonequivalence we find a string in one set but not in the
other.) Or (ii) we use the identities to prove the equivalence of P and Q. Or
(iii) we construct the corresponding FA M and M' and prove that M and M' are
equivalent. (For nonequivalence we prove that M and lvi' are not equivalent.)
The method to be chosen depends on the problem.
EXAMPLE 5.1 7
Prove (a + b)* = a*(ba*)*.
Solution
Let P and Q denote (a + b)* and a*(ba*)*, respectively. Using the construction
in Section 5.2.5, P is given by the transition system depicted in Fig. 5.25.
A
a, b
I-----A---..{O
a, b
Fig. 5.25 Transition system for (a + b)*.
The transition system for Q is depicted in Fig. 5.26.
It should be noted that Figs. 5.25 and 5.26 are obtained after eliminating
A-moves. As these two transition diagrams are the same, we conclude that
P = Q.
. ..
We now summarize all the results and constructions given in this section.
(i) Every r.e. is recognized by a transition system (Theorem 5.2).
(ii) A transition system M can be converted into a finite automaton
accepting the same set as M (Section 5.2.3).
(iii) Any set accepted by finite automaton is represented by an r.e.
(Theorem 5.3).
(iv) A set accepted by a transition system is represented by an r.e. (from
(ii) and (iii».