Compiler Design and Construction - Old Questions

3.  Convert the regular expression '0 +(1+ 0)*00' first into NFA and then into DFA using Thomson’s and Subset Construction methods.

Given RE:

0 +(1+ 0)*00

Converting into NFA using Thomson's method:

For 0,

For 1,

For 1+0

For (1+0)*

For (1+0)*00

For 0+(1+0)*00

Which is the required NFA. Now converting it into a DFA:

The initial state of the NFA is {A}.

Therefore, the initial state of the DFA is:

S₀ = ∈-closure({A}) = {A, B, C, D, E, F, J}

Here,

Σ = {0, 1)

Now,

Dtran[S₀, 0] = ∈-closure(move(S₀, 0)) = ∈-closure({H, K, M}) = {D, E, F, H, I, J, K, M, N} = S₁ (say)

Dtran[S₀, 1] = ∈-closure(move(S₀, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Dtran[S₁, 0] = ∈-closure(move(S₁, 0)) = ∈-closure({H, K, L}) = {D, E, F, H, I, J, L, N} = S₃

Dtran[S₁, 1] = ∈-closure(move(S₁, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Dtran[S₂, 0] = ∈-closure(move(S₂, 0)) = ∈-closure({H, K}) = {D, E, F, H, I, J, K} = S₄

Dtran[S₂, 1] = ∈-closure(move(S₂, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Dtran[S₃, 0] = ∈-closure(move(S₃, 0)) = ∈-closure({H, K}) = {D, E, F, H, I, J, K} = S₄

Dtran[S₃, 1] = ∈-closure(move(S₃, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Dtran[S₄, 0] = ∈-closure(move(S₄, 0)) = ∈-closure({H, K, L}) = {D, E, F, H, I, J, L, N} = S₃

Dtran[S₄, 1] = ∈-closure(move(S₄, 1)) = ∈-closure({G}) = {D, E, F, G, I, J} = S₂

Here, S₁ & S₃ are the accepting state of DFA, since N is a member of both S₁ & S₃ states.

The equivalent DFA is;