# Theory of Computation – Construction of Regular Expressions from Deterministic Finite Automata

«
»
We know that for every regular expression there exist a deterministic finite automaton. So we can say that regular languages, regular expressions and finite automata are all different representation of the same thing. Earlier we learnt how to convert a regular expression into a finite automaton; in this tutorial we will learn how to convert a given finite automaton to a regular expression. For that we must first learn about Arden’s Theorem.

Arden’s Theorem
Let P and Q be two regular expressions over alphabet Σ. If P does not contain null string, then
R = Q + RP
has a unique solution that is R = QP*
Proof:
Put the value of R in the R.H.S.
R = Q + (Q + RP)P = Q + QP + RP2
When we put the value of R again and again we get the following equation
R = Q + QP + QP2 + QP3…..
R = Q(1 + P + P2 + P3 + ….
R = Q(є + P + P2 + P3 + ….
The second part of the product on the L.H.S can be replaced with the kleen closure. So the equation becomes
R = QP*

Using Arden’s Theorem to find Regular Expression of a Deterministic Finite automata

1. For getting the regular expression for the automata we first create equations of the given form for all the states
q1 = q1w11 + q2w21 + … + qnwn1 + є (q1 is the initial state)
q2 = q1w12 + q2w22 + … + qnwn2
. .
. .
. .
qn = q1w1n + q2w2n + … + qnwnn
wij is the regular expression representing the set of labels of edges from qi to qj
Note: for parallel edges there will be that many expressions for that state in the expression.
2. Then we solve these equations to get the equation for qi in terms of wij and that expression is the required solution, where qi is a final state.

Assumptions made while forming the regular expression

1. The transition diagram should not have є – transitions
2. It must have only a single initial state

Let us see an example to demonstrate this method

Example: Draw a FA that accepts strings containing exactly 1 over alphabet {0, 1} and write a regular expression for the same.

The FA for the above language will be: Now let us form the equation
q1 = q10 + є
q2 = q11 + q20
q3 = q21 + q30 + q31
Solving the equations
q1 = є0* (using Arden’s theorem; here Q = є , P = 0, R = q1)
q1 = 0*
q2 = 0*1 + q20
q2 = 0*1(0)* (here Q = 0*1, P = 0, R = q2)
Hence, 0*10* is the regular expression for the above deterministic finite automaton.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Note: We need not consider a trap state in our equations as it does not contribute to the regular expression

Given below are few questions for you to practice.

Question1: Construct a regular expression corresponding to the automata given below Let us form the equations
q1 = q10 + q30 + є
q2 = q11 + q21 + q31
q3 = q20
Solving the equations
q2 = q11 + q21 + (q20)1 = q11 + q2(1 + 01)
q2 = q11 (1 + 01)*
So, q1 = q10 + q30 + є
q1= q10 + q11(1 + 01*)00 + є
= q1(0 + 1(1 + 01)*00) + є
= є (0 + 1(1 + 01)*00)*
q1=(0 + 1(1 + 01)*00)*
So the regular expression for the given automata is =(0 + 1(1 + 01)*00)*
Question 2: Derive a regular expression for the language containing strings ending in 1 but not containing substring 00.
The deterministic finite automata for the language is The equations for the above automata are:
q1 = є
q2 = q10 + q30
q3 = q11 + q21 + q3 1
Solving the above equations to get the regular expression
q2 = 0 + q30
q3 = 1 + 01 + q301 + q31
= (1 + 01) + q3(01 + 1)
q3 = (1 + 01) (1 + 01)*
(1 + 01)+ is the regular expression for the given language

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials. 