Construct NFA and Convert to DFA Using Algorithm L = aA + bbC

Solution

NFA for the above language will be −

Conversion from NFA to DFA −

ε − closure(0) = {0, 1, 4} = A

For State A


For input symbol a For input symbol b For input symbol c
∴ Ta = {2} ∴ Tb = {5} Tc = ∅
∴ ε − closure (Ta)
                       = ε
                      − closure (2)
= {2} = B		 ∴ ε − closure (Tb)
                        = ε
                        − closure (5)
= {5, 6, 8, 9, 11, 12} = C		 ∴ ε − closure (∅) = ∅
                  = D

For State B


For input symbol a For input symbol b For input symbol c
∴ Ta = {3} ∴ Tb = {} Tc = {}
∴ ε − closure (3) =
= {3, 12} = E		  ∴ ε − closure (Tb) = { }
= ∅ = D		 ∴ ε − closure (Tc) = ∅ = D

For State C


For input symbol a For input symbol b For input symbol c
∴ Ta = {} ∴ Tb = {7} Tc = {10}
∴ ε − closure (Ta) =
∅ = D		 ∴ ε − closure (7)
 = { 7, 8, 6, 9, 11, 12}
= F		 ∴ ε − closure (10)
                  = {10, 9, 11, 12}
                  = G

For State E


∴ Ta = ∅ ∴ Tb = ∅ Tc = ∅
∴ ε − closure (Ta) =
             ∅ = D		 ∴ ε − closure (Tb) =
                ? = D		 ∴ ε − closure (Tc) =
               ? = D

For State F


∴ Ta = ∅ ∴ Tb = {7} Tc = {10}
∴ ε − closure (Ta) =
        ∅ = D		 ∴ ε − closure (Tb) =
 = ε − closure (7)
= {7,8,6,9,12}
= F		 ∴ ε − closure (10) =
    {10, 9, 11, 12} = G

For State G


∴ Ta = ∅ ∴ Tb = {7} Tc = {10}
∴ ε − closure (?) = ?
= D		 ∴ ε − closure (?) = ? =
 D		 ∴ ε − closure (10) =
 G

For State D

D = ∅

Ta = Tb = Tc = ∅

ε − closure (Ta) = ε − closure (Tb) = ε − closure (Tc) = ? = D

Transition Table and Diagram for DFA will be −

(Initial State)



 a B c Here
A B C D A = {0,1,4}
B E D D B = {2}
C D F G C = {5,6,8,9,11,12}
D D D D D = ∅
E D D D E = {3, 12}
F D F G F = {7,8,6,9,11,12}
G D D G G = {10,9,11,12}










Updated on: 2021-10-29T08:28:42+05:30

1K+ Views

Kickstart Your Career

Get certified by completing the course

Get Started
Advertisements