in order to find out a regular expression of a finite automaton, we use arden’s theorem along with the properties of regular expressions.

statement −

let p and q be two regular expressions.

if p does not contain null string, then r = q + rp has a unique solution that is r = qp*

proof −

r = q + (q + rp)p [after putting the value r = q + rp]

= q + qp + rpp

when we put the value of r recursively again and again, we get the following equation −

r = q + qp + qp² + qp³…..

r = q (ε + p + p² + p³ + …. )

r = qp* [as p* represents (ε + p + p2 + p3 + ….) ]

hence, proved.

assumptions for applying arden’s theorem

• the transition diagram must not have null transitions
• it must have only one initial state

method

step 1 − create equations as the following form for all the states of the dfa having n states with initial state q₁.

q₁ = q₁r₁₁ + q₂r₂₁ + … + q_nr_n1 + ε

q₂ = q₁r₁₂ + q₂r₂₂ + … + q_nr_n2

…………………………

…………………………

…………………………

…………………………

q_n = q₁r_1n + q₂r_2n + … + q_nr_nn

r_ij represents the set of labels of edges from q_i to q_j, if no such edge exists, then r_ij = ∅

step 2 − solve these equations to get the equation for the final state in terms of r_ij

problem

construct a regular expression corresponding to the automata given below −

solution −

here the initial state and final state is q₁.

the equations for the three states q1, q2, and q3 are as follows −

q₁ = q₁a + q₃a + ε (ε move is because q1 is the initial state0

q₂ = q₁b + q₂b + q₃b

q₃ = q₂a

now, we will solve these three equations −

q₂ = q₁b + q₂b + q₃b

= q₁b + q₂b + (q₂a)b (substituting value of q₃)

= q₁b + q₂(b + ab)

= q₁b (b + ab)* (applying arden’s theorem)

q₁ = q₁a + q₃a + ε

= q₁a + q₂aa + ε (substituting value of q₃)

= q₁a + q₁b(b + ab*)aa + ε (substituting value of q₂)

= q₁(a + b(b + ab)*aa) + ε

= ε (a+ b(b + ab)*aa)*

= (a + b(b + ab)*aa)*

hence, the regular expression is (a + b(b + ab)*aa)*.

problem

construct a regular expression corresponding to the automata given below −

solution −

here the initial state is q₁ and the final state is q₂

now we write down the equations −

q₁ = q₁0 + ε

q₂ = q₁1 + q₂0

q₃ = q₂1 + q₃0 + q₃1

now, we will solve these three equations −

q₁ = ε0* [as, εr = r]

so, q₁ = 0*

q₂ = 0*1 + q₂0

so, q₂ = 0*1(0)* [by arden’s theorem]

hence, the regular expression is 0*10*.