**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 + RP^{2}

When we put the value of R again and again we get the following equation

R = Q + QP + QP^{2} + QP^{3}…..

R = Q(1 + P + P^{2} + P^{3} + ….

R = Q(є + P + P^{2} + P^{3} + ….

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**

- For getting the regular expression for the automata we first create equations of the given form for all the states

q_{1}= q_{1}w_{11}+ q_{2}w_{21}+ … + q_{n}w_{n1}+ є (q_{1}is the initial state)

q_{2}= q_{1}w_{12}+ q_{2}w_{22}+ … + q_{n}w_{n2}

. .

. .

. .

q_{n}= q_{1}w_{1n}+ q_{2}w_{2n}+ … + q_{n}w_{nn}

w_{ij}is the regular expression representing the set of labels of edges from q_{i}to q_{j}

Note: for parallel edges there will be that many expressions for that state in the expression. - Then we solve these equations to get the equation for q
_{i}in terms of w_{ij}and that expression is the required solution, where q_{i}is a final state.

**Assumptions made while forming the regular expression**

- The transition diagram should not have є – transitions
- 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.**

View Answer

Now let us form the equation

q

_{1}= q

_{1}0 + є

q

_{2}= q

_{1}1 + q

_{2}0

q

_{3}= q

_{2}1 + q

_{3}0 + q

_{3}1

Solving the equations

q

_{1}= є0* (using Arden’s theorem; here Q = є , P = 0, R = q

_{1})

q

_{1}= 0*

q

_{2}= 0*1 + q

_{2}0

q

_{2}= 0*1(0)* (here Q = 0*1, P = 0, R = q

_{2})

Hence, 0*10* is the regular expression for the above deterministic finite automaton.

**Advertisement: Join Sanfoundry@Linkedin**

**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**

View Answer

q

_{1}= q

_{1}0 + q

_{3}0 + є

q

_{2}= q

_{1}1 + q

_{2}1 + q

_{3}1

q

_{3}= q

_{2}0

Solving the equations

q

_{2}= q

_{1}1 + q

_{2}1 + (q

_{2}0)1 = q

_{1}1 + q

_{2}(1 + 01)

q

_{2}= q

_{1}1 (1 + 01)*

So, q

_{1}= q

_{1}0 + q

_{3}0 + є

q

_{1}= q

_{1}0 + q

_{1}1(1 + 01*)00 + є

= q

_{1}(0 + 1(1 + 01)*00) + є

= є (0 + 1(1 + 01)*00)*

q

_{1}=(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.**

View Answer

The equations for the above automata are:

q

_{1}= є

q

_{2}= q

_{1}0 + q

_{3}0

q

_{3}= q

_{1}1 + q

_{2}1 + q

_{3}1

Solving the above equations to get the regular expression

q

_{2}= 0 + q

_{3}0

q

_{3}= 1 + 01 + q

_{3}01 + q

_{3}1

= (1 + 01) + q

_{3}(01 + 1)

q

_{3}= (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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!