# CS606 VU Assignment No. 1 Spring 2012 Solution

Construct Nondeterministic finite automata (NFA) for regular expression (a* | b*)* using Thompson’s Construction Algorithm. Show the sequence of moves in processing the input string “ababbab”.

For the NFA given below, you are required to determine an equivalent DFA for it using subset
construction. Where the alphabet is {a, b}

Solution :-

E-closure ({1})={2,3,4,6,9.10,12}=A

E-closure(move{2,3,4,6,9.10,12},a)= E-closure({5})={5,8,3,4,6,9,10}=B

E-closure(move{2,3,4,6,9.10,12},b)= E-closure({7})={7,8,3,4,6,9,10}=C

E-closure(move{2,3,4,6,9.10,12},c)= E-closure({11})={14}=D

E-closure(move{2,3,4,6,9.10,12},d)= E-closure({13})={14}=D

E-closure(move{5,8,3,4,6,9,10},a)= E-closure({5})={5,8,3,4,6,9,10}=B

E-closure(move{5,8,3,4,6,9,10},b)= E-closure({7})={7,8,3,4,6,9,10}=C

E-closure(move{5,8,3,4,6,9,10},c)= E-closure({11})={14}=D

E-closure(move{5,8,3,4,6,9,10},d)= E-closure({ })={ }

E-closure(move{7,8,3,4,6,9,10},a)= E-closure({5})={5,8,3,4,6,9,10}=B

E-closure(move{7,8,3,4,6,9,10},b)=E-closure({7})={7,8,3,4,6,9,10}=C

E-closure(move{7,8,3,4,6,9,10},c)= E-closure({11})={14}=D

E-closure(move{7,8,3,4,6,9,10},d)= E-closure({ })={  }

E-closure(move{14},a)= E-closure({ })={  }

E-closure(move{14},b)= E-closure({ })={  }

E-closure(move{14},c)= Î-closure({ })={  }

E-closure(move{14},d)= Î-closure({ })={  }

A={2,3,4,6,9.10,12}

B={5,8,3,4,6,9,10}

C={7,8,3,4,6,9,10}

D={14}

The transition table of the DFA   is

 a b c d A B C D D B B C D {} C B C D {} D {} {} {} {}

The resulting DFA  is