Compiler Design and Construction - Old Questions

4.  Given a regular expression (a+∈) bc*. Construct the DFA recognizing the pattern described by the regular expression using syntax tree based reduction.

Given RE;

(a+∈) bc*

The augmented RE of the given RE is:

(a+∈) bc* #

Syntax tree for augmented R.E. is

Calculating followpos:

followpos(1) = {2}

followpos(2) = {3, 4}

followpos(3) = {3, 4}

Now,

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

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

2) From S₀ = {1, 2}

    1  represents 'a'

    2 represents 'b'

followpos(1) = {2} = S₁

     δ(s₀, a) = S₁

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

    δ(S₀, b) = S₂

3) From S₁ = {2}

    Here 2 represents 'b'

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

     δ(S₁, b) = S₂

4) From S₂ = {3, 4}

    Here 3 represents 'c'

    4 represents '#'

followpos(3) = {3, 4} = S₂

    δ(S₂, c) =  S₂

Now there was no new states occur.

Therefore, Final state = {S₂}

Now the resulting DFA of given regular expression is: