Algorithms for Compiler Design: OBTAINING THE REGULAR EXPRESSION FROM THE FINITE AUTOMATA

Given a finite automata, to obtain a regular expression that specifies the regular set accepted by the given finite automata, the following steps are necessary:

1. Associate suitable variables (e.g., A, B, C, etc.) with the states of finite automata.

2. Form a set of equations using the following rules:

   1. If there exists a transition from a state associated with variable A to a state associated with variable B on an input symbol a, then add the equation

      

   2. If the state associated with variable A is a final state, add A = ∈ to the set of equations.

   3. If we have the two equations A = ab and A = bc, then they can be combined as A = aB | bc.

3. Solve these equations to get the value of the variable associated with the starting state of the automata. In order to solve these equations, it is necessary to bring the equation in the following form:

   

where S is a variable, and a and b are expressions that do not contain S. The solution to this equation is S = a*b. (Here, the concatenation operator is between a* and b, and is not explicitly shown.) For example, consider the finite automata whose transition diagram is shown in Figure 1.

Figure 1: Deriving the regular expression for a regular set.

We use the names of the states of the automata as the variable names associated with the states.

The set of equations obtained by the application of the rules are:

To solve these equations, we do the substitution of (II) and (III) in (I), to obtain:

Therefore, the value of variable S comes out be:

Therefore, the regular expression specifying the regular set accepted by the given finite automata is