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

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