Compiler Design and Construction - Old Questions

2.  Convert the following RE to DFA directly.

                (a+b)*ab

Given RE;

(a+b)*ab

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}

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 'a'

    2 represents 'b'

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

    δ(s₀, a) = S₁

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

    δ(S₀, b) = S₀

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

    1, 3 → a

    2, 4 → b

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

     δ(S₁, a) = S₁

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

     δ(S₁, b) = S₂

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

    1, 3 → a

    2 → b

    5 → #

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

    δ(S₂, a) = S₁

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

     δ(S₂, b) = S₀

Now there was no new states occur.

Therefore, Final state = {S₂}

Now the resulting DFA of given regular expression is: