Arden’s theorem examples and Conversion of finite automata to regular expression

Figure (1): Transaction Diagram

Consider the Transaction diagram (1), covert it to an equivalent regular expression using Arden’s Theorem.

We can directly apply the Arden’s procedure directly since the graph does not contain any ε-moves and there is only one initial state.

The three equations for q₁, q₂ and q₃ can be written as;

q₁ = q₁a + q₂b + ε                     —– (1)
q₂ = q₁a + q₂b + q₃a                 —– (2)
q₃ = q₂a                                     —– (3)

It is necessary to reduce the number of unknowns by repeated substitution. By substituting q3 in the q2-equation, we get by applying Arden’s Theorem:

q₂ = q₁a + q₂b + q₂aa
= q₁a + q₂ (b + aa)
= q₁a (b + aa)*

Substituting q2 in q1, we get

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

Hence,
q₁  = ε (a + a(b + aa)*b)*
q₂  = (a + a(b + aa)*b)* a(b + aa)*
q₃  = (a + a(b + aa)*b)* a(b + aa)*a

Since q3 is a final state, the set of strings recognized by the transaction graph is given by

            (a + a(b + aa)*b)* a(b + aa)*a

Figure (2): Transaction Diagram

Consider the Transaction diagram (2), covert it to an equivalent regular expression using Arden’s Theorem.

We can directly apply the Arden’s procedure directly since the graph does not contain any ε-moves and there is only one initial state.

The three equations for q₁, q₂ and q₃ can be written as;

q₁ = q₁0 + ε                  —– (1)
q₂ = q₁1 + q₂1               —– (2)
q₃ = q₂0 + q₃ (0+1)       —– (3)
By applying Arden’s Theorem to equation (1), we get
q₁ = q₁0 + ε      =          ε0*
So,
q₂ = q₁1 + q₂1 = 0*1 + q₂1
Therefore,
q₂ = (0*1)1*
As the final states are q₁ and q₂, we need not solve for state q₃:
q₁ + q₂ = 0* + 0*(11*) = 0*(ε + 11*) = 0*(1*) = 0*1*

Also check: cfg examples with solutions

Figure (3): Transaction Diagram

Consider the Transaction diagram (3), covert it to an equivalent regular expression using Arden’s Theorem.

We can directly apply the Arden’s procedure directly since the graph does not contain any ε-moves and there is only one initial state.

The three equations for q₁, q₂ and q₃ can be written as;

q₁ = q₁0 + q₃0 + ε                     —– (1)
q₂ = q₁1 + q₂1 + q₃0                 —– (2)
q₃ = q₂0                                                —– (3)
So,
q₂ = q₁1 + q₂1 + (q₂0)1
= q₁1 + q₂ (1 + 01)
By applying Arden’s Theorem, we get
q₂ = q₁1(1 + 01)*
Also,
q₁ = q₁0 + q₃0 + ε
=  q₁0 + q₂00 + ε
= q₁0 + (q₁ 1(1 + 01)*)00 + ε
= q₁ (0 + 1(1 + 01)*00) + ε

Once again applying Arden’s Theorem, we get;

q₁ = ε (0 + 1(1 + 01)* 00)*
= ε (0 + 1(1 + 01)* 00)*

∵q₁ is the only final state, the regular expression corresponding to the given diagram is (0 + 1(1 + 01)* 00)*.

Figure (4): Transaction Diagram

Consider the Transaction diagram (4), covert it to an equivalent regular expression using Arden’s Theorem.

We can directly apply the Arden’s procedure directly since the graph does not contain any ε-moves and there is only one initial state.

The four equations for q₁, q₂ q₃ and q₄ can be written as;

q₁ = q₁0 + q₃0 + q₄0 + ε           —– (1)
q₂ = q₁1 + q₂1 + q₄1                 —– (2)
q₃ = q₂0                                     —– (3)
q₄ = q₃1                                     —– (4)

Now,

q₄ = q₃1 = (q₂0)1 = q₂01                 —– (4)
Thus, we able to write q₃, q₄ in terms of q₂. Using the equation (2), we get

q₂ = q₁1 + q₂1 + q₂011
= q₁1 + q₂ (1 + 011)

By applying the Arden’s Theorem, we get

q₂ = (q₁1)(1 + 011)*
= q₁ (1(1 + 011)*)

From the equation (1), we get;

q₁ = q₁0 + q₂00 + q₂010 + ε                  —– (1)
= q₁0 + q₂(00 + 010) + ε
= q₁0 + q₁1(1 + 011)*(00+010) + ε

Again, by applying Arden’s Theorem, we get

q₄ = q₂01

= q₁1(1 + 011)*01
= (0+ 1(1 + 011)*(00+010))*(1(1+011)*01)