How to convert finite automata to regular expressions

Every finite automaton has an equivalent regular expression.

The conversion of a finite automaton to a regular expression is done through the state elimination method.

State elimination method

The State elimination method follows the following general set of rules:

1. Add a new initial state ($I$). Make a null transition from the old initial state to the new initial state.
2. Add a new final state ($F$). Make null transition(s) to the new final state.
3. Eliminate all states, except $I$ and $F$, in the given finite automaton. Perform the elimination of states by checking the in-degreesA transition into a state and out-degreesA transition moving away from a state of states and taking a cross product.

After steps 1 and 2, the $I$ state will not have any inward transitions, and the state $F$ state will not have any outward transitions.

Example

Let's consider the following finite automaton:

Step 1: Add an initial state

Add a new initial state, $I$. Make a null transition from state $I$ to state $q_0$.

Step 2: Add a final state

Add a new final state, $F$. Make a null transition from state $q_3$ to state $F$.

Step 3: State elimination

Perform the elimination of states other than $I$ and $F$.

Step 3.1

Eliminate state $q_0$.

Step 3.2

Eliminate state $q_3$_. Concatenate transitions from state $q_3$ to state $F$ as per the basic rules of writing regular expressions.

Step 3.3

Eliminate $q_1$. Check for the in-degree and out-degree of state $q_1$. Write the regular expressions for the new transitions acquired after removing state $q_1$.

Step 3.4

Eliminate state $q_2$.

Step 3.5

Put it all together.

Result

The resultant regular expression for the given finite automaton is as follows:

$a.a*.(a + b) + ((a.a*.a) + b).(b.a*.a)*.b.a*.(a + b)$.