DFA without constructing NFA
Again, DFA without Constructing NFA is the Important topic of the Compiler Design.

Construct DFAInitial node = firstpos (root node) {1,2,3} — Anode)= δ(A,a) = followpos(1) U followpos(3)(A,a) = {1,2,3} U {4} = {1,2,3,4} — B δ (A,b) = followpos(2) = {1,2,3} — A δ (B,a) = followpos(1) U followpos(3) = {1,2,3} U {4} = {1,2,3,4} — B δ(B,b) = followpos(2) U followpos(4)(B,b) = {1,2,3} U {5} = {1,2,3,5} — C δ(C,a) = followpos(1) U followpos(3)(C,a) = {1,2,3} U {4} = {1,2,3,4} — B δ(C,b) = followpos(2) U followpos(5)(C,b) = {1,2,3} U {6} = {1,2,3,6} — D δ(D,a) = followpos(1) U followpos(3)(D,a) = {1,2,3} U {4} = {1,2,3,4} — B δ(D,b) = followpos(2) = {1,2,3}—A(D,b) Ex:2 a*b*a(a\b)*b*a#b)*b*a# Syntax tree for a*b*a(a\b)*b*a#
Construct DFAInitial node = firstpos (root node) {1,2,3} — Anode)= δ (D,a) = followpos(1) U follow pos (3) U followpos( 7) U followpos( 4 )= {1,2,3} U {4,5,6,7} U {8} U {4,5,6,7} DFA: 
Related Search
Compiler Design, Thompson’s rule, Finite Automata, Free Study.
Leave a Reply