Compiler Design and Construction - Old Questions

6. Given a regular expression (ε + 0)*10. Construct the DFA recognizing the pattern described by this regular expression using syntax tree based reduction.

Given RE;

(ε + 0)*10

The augmented RE of the given RE is:

(ε + 0)*10 #

Syntax tree for augmented R.E. is

Calculating followpos:

followpos(1) = {1, 2}

followpos(2) = {3}

followpos(3) = {4}

Now,

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

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

2) From S0 = {1, 2}

    1  represents '0'

    2 represents '1'

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

     δ(s0, 0) = S0

followpos(2) = {3} = S1

    δ(S0, 1) = S1

3) From S1 = {3}

    Here 3 represents '0'

followpos(3) = {4} = S2

     δ(S1, 0) = S2

4) From S2 = {4}

    Here 4 represents '#'

Now there was no new states occur.

Therefore, Final state = {S2}

Now the resulting DFA of given regular expression is: