Sunday, December 18, 2011

Finite Automaton to Regular Expression


Example: -Find out Regular Expression for Given Finite Automaton.


Solution:

Equations Used in Calculation

For Table -1 :

L (p, q, 0) = {a є Σ | δ (p, a) = q}              if  p ≠ q
L (p, q, 0) = {a є Σ | δ (p, a) = p} U {Λ}  if  p = q

For Other Tables:

L (p, q, k+1) = L (p, q, k) U L (p, k+1, k) L (k+1, k+1, k)* L (k+1, q, k)

Table – 1 :


p
r ( p , 1 , 0 )
r ( p , 2 , 0 )
r ( p , 3 , 0 )
1
Λ + b
a
Φ
2
Φ
Λ + a
b
3
b
a
Λ


Table – 2 :

p
r ( p , 1 , 1 )
r ( p , 2 , 1 )
r ( p , 3 , 1 )
1
(Λ + b) (Λ + b)*
(Λ + b)* a
Φ
2
Φ
Λ + a
b
3
b (Λ + b)*
b* a
Λ



Table – 3 :

p
r ( p , 1 , 2 )
r ( p , 2 , 2 )
r ( p , 3 , 2 )
1
(Λ + b) (Λ + b)*
(Λ + b)* a (Λ + a )*
(Λ + b)* a (Λ + a )* b
2
Φ
 (Λ + a ) (Λ + a )*
(Λ + a )* b
3
b (Λ + b)*
b* a (Λ + a )*
Λ + b* a (Λ + a )* b


Final Calculation:

For Final Answer the Equation is as per follows.

L (Initial State, Final State, Total No. of States)

L (p, q, k+1) = L (p, q, k) U L (p, k+1, k) L (k+1, k+1, k)* L (k+1, q, k)

L(1,3,3)
= L(1,3,2) U L(1,3,2) L(3,3,2)* L(3,3,2)
= ( (Λ + b)* a (Λ + a )* b ) +
    ((Λ + b)* a (Λ + a )* b (Λ + b* a (Λ + a )* b)*  (Λ + b* a (Λ + a )* b )
= ( (Λ + b)* a (Λ + a )* b ) (Λ + (Λ + b* a (Λ + a )* b)*  (Λ + b* a (Λ + a )* b ) )
= ( b* a a* b ) (Λ + b* a (Λ + a )* b)*
= ( b* a a* b ) (Λ + b* a a* b)*
= ( b* a* a b ) (Λ + b* a* a b)*
= ( b* a* a b )+
= (b* a* )+ a b
= (b* a* )* a b      [ (a*b*)+ =  (a*b*)* ]
= ( a + b )* a b      [ (a*b*)* = (a + b)*]


Note :
 For example suppose 2 and 3 both are final states in above example. Then Final Regular Expression we can get from following Equation
                               L(1, 2, 3)  + L(1, 3, 3) 


No comments:

Post a Comment