Compiler Design and Construction - Old Questions

3.  Given the regular expression (0 + 1)* 011 , construct a DFA equivalent to this regular expression computing follow pos ().

Given RE;

(0 + 1)* 011

The augmented RE of the given RE is:

Syntax tree for augmented R.E. is

Calculating followpos:

followpos(1) = {1, 2, 3}

followpos(2) = {1, 2, 3}

followpos(3) = {4}

followpos(4) = {5}

followpos(5) = {6}

Now,

1) Start state of DFA = firstpos(root) = {1, 2, 3} = S₀

Use followpos of symbol representing position in RE to obtain the next state of DFA.

2) From S₀ = {1, 2, 3}

    1 and 3 represents '0'

    2 represents '1'

followpos({1, 3}) = {1, 2, 3, 4} = S₁

    δ(s₀, 0) = S₁

followpos({2}) = {1, 2, 3} = S₀

    δ(S₀, 1) = S₀

3) From S₁ = {1, 2, 3, 4}

    1, 3 → 0

    2, 4 → 1

followpos({1, 3}) = {1, 2, 3, 4} = S₁

     δ(S₁, 0) = S₁

followpos({2, 4}) = {1, 2, 3, 5} = S₂

     δ(S₁, 1) = S₂

4) From S₂ = {1, 2, 3, 5}

    1, 3 → 0

    2, 5 → 1

followpos({1, 3}) = {1, 2, 3, 4}= S₁

    δ(S₂, 0) = S₁

followpos({2, 5}) = {1, 2, 3, 6} = S₃

     δ(S₂, 1) = S₃

5) From S₃ = {1, 2, 3, 6}

    1, 3 → 0

    2 → 1

    6 → #

followpos({1, 3}) = {1, 2, 3, 4}= S₁

    δ(S₃, 0) = S₁

followpos({2}) = {1, 2, 3} = S₀

    δ(S₃, 1) = S₀

Now there was no new states occur.

Therefore, Final state = {S₃}

Now the resulting DFA of given regular expression is: