TOC : Rules for Constructing Arden's Equation | Class-14

📌Highlights: Hello Friends ! In this we explain about Rules for Constructing Arden's Equation.This post cover following such as All rules of Arden's Equation, Example of converting RE to FA by applying these rules.

Let we have any Finite Automata (FA) which follow certain rules.

1. Finite Automata does not contain ∈

    Note: This is only done in DFA. If the automata is NDFA than first convert it                   into DFA then apply

    Know how to convert NDFA to DFA

2. Suppose states or vertices are represented as

        v1, v2, v3, -----------, vn.

    i.e Automata contains n-number of states.

3. α_ij represent the RE which is constructed by level of edge from v_i to v_j.

    If there is no edge from v_i to v_j than α_ij = φ

    Then Arden's equation can be written as 

After the construction of Arden's equation , Now repeatedly substitution of equation and repeatedly applying Arden's result we found RE of many states or vertices in form of (set of I/P symbol)

Now select the RE of final state which is our required result.

Example:

1. Construct RE to FA

    q₁ = q₁ 0 + q₃ 0 + ∈ -------------------Equation 1

    q₂ = q₁₁ 1 + q₂ 1 + q₃ 1  --------------Equation 2

    q₃ = q₂ 0   ------------------------------Equation 3

Put value of equation 3 in equation 2

    q₂ = q₁₁ 1 + q₂ 1 + q₂ 01 

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

Apply Arden's theorem

    q₂ =  q₁ 1  (1 + 01)^* ------------- Equation 4

Put the value of q3  in equation 1

    q₁ =  q₁ 0 + q₂ 00 + ∈

Again put value of equation 4 in the above

    q₁ =  q₁ 0 + q₁ 1(1 + 01)^* 00 + ∈ 

    q₁ =  q₁(0 + 1 (1 + 01)^* 00) + ∈ 

_{Now apply Arden's theorem}

    q₁ =  ∈  (0 + 1 (1 + 01)^* 00)^* 

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

2. Construct a RE to FA.

    q₁ =  q₁ 0 + q₄ 0 + q₃ 0 + ∈ ------------Equation 1

    q₂ =  q₂ 1 + q₁ 1 + q₄ 1 ----------------Equation 2

    q₃ =  q₂ 0 ----------------------------Equation 3

    q₄ =  q₃ 1 ----------------------------Equation 4

Put the value of equation 4  in equation 2

    q₂ =  q₂ 1 + q₁ 1 + q₃ 11 ---------------Equation 5

Put value of equation 3 in equation 5

    q₂ =  q₂ 1 + q₁ 1 + q₂ 011

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

Apply Arden's theorem

    q₂ =  q₁ 1(1 + 011)^* -------------------Equation 6

Put the value of equation 6 in equation 3

    q₂ =  q₁ 1(1 + 011)^* 0  -----------------Equation 7

Put the value of equation 7  in equation 4

    q₄ =  q₁ 1(1 + 011)^* 0  -----------------Equation 8

Put the value of equation 7 and 8  in equation 1

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

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

Now apply Arden's theorem

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

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

Friend this is all about Rules for Constructing Arden's Equation. The above Examples demonstrate how to implement Arden's Rules. We will meet in  new next post ! till thanks !