5. If the GTG has four or more states, pick a state q k to be removed. Apply rule
4 for all pairs of states (q i ,q j ),i ≠ k, j ≠k. At each step
apply the simplifying rules
r + Ø=r,
rØ = Ø,
Ø*= λ,
wherever possible. When this is done, remove state qk.
6. Repeat Steps 3 to 5 until the correct regular expression is obtained.
Example 3.11
Find a regular expression for the language
L = {w ∈{a, b}* : n a (w) is even and n b (w) is odd}.
An attempt to construct a regular expression directly from this description leads
to all kinds of difficulties. On the other hand, finding an nfa for it is easy as long
as we use vertex labeling effectively. We label the vertices with EE to denote an
even number of a’s and b’s, with OE to denote an odd number of a’s and an even
number of b’s, and so on. With this we easily get the solution which, after
conversion into a complete generalized transition graph, is in Figure 3.13.
We now apply the conversion to a regular expression, using procedure nfato-rex. To remove the state OE, we apply Equation (3.3). The edge between EE
and itself will have the label
We continue in this manner until we get the GTG in Figure 3.14. Next, the state
OO is removed, which gives Figure 3.15. Finally, we get the correct regular
expression from Equation (3.2).
Figure 3.13