Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

How to convert finite automata to regular expressions

Ayesha Kanwal

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 (II). Make a null transition from the old initial state to the new initial state.
  2. Add a new final state (FF). Make null transition(s) to the new final state.
  3. Eliminate all states, except II and FF, 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 II state will not have any inward transitions, and the state FF state will not have any outward transitions.

Example

Let's consider the following finite automaton:

Finite automaton

Step 1: Add an initial state

Add a new initial state, II. Make a null transition from state II to state q0q_0.

Adding state I

Step 2: Add a final state

Add a new final state, FF. Make a null transition from state q3q_3 to state FF.

Adding state F

Step 3: State elimination

Perform the elimination of states other than II and FF.

Step 3.1

Eliminate state q0q_0.

Eliminating q0

Step 3.2

Eliminate state q3q_3. Concatenate transitions from state q3q_3 to state FF as per the basic rules of writing regular expressions.

Eliminating q3

Step 3.3

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

Eliminating q1

Step 3.4

Eliminate state q2q_2.

Eliminating q2

Step 3.5

Put it all together.

The final regular expression

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)a.a*.(a + b) + ((a.a*.a) + b).(b.a*.a)*.b.a*.(a + b).

RELATED TAGS

RELATED COURSES

View all Courses

Keep Exploring