Thursday, 17 November 2011

CS 402_2nd Assignment Solution


Question # 1:
Using the FA’s corresponding to r1  and r2, Build an FA corresponding to

a r1+ r2  (Union of r1  and  r2).
b)   r1r2  (Concatenation of r1  and r2).
c r1* (Closure of r1).




Solution:
r1+ r2  (Union of r1  and  r2).


New States
Old States


A
B
Z1-  º (x1,x1)
(x2,x2)  º Z2
(x3,x1)  º Z3
Z2  º (x2,x2)
(x3.x2)  º Z4
(x4,x3)  º Z5
Z3  º (x3,x1)
(x3,x2)  º Z4
(x3,x1)  º Z3
Z4  º (x3,x2)
(x3,x2)  º Z4
(x3,x3)  º Z6
Z5+  º (x4,x3)
(x4,x2)  º Z7
(x4,x1)  º Z8
Z6+  º (x3,x3)
(x3,x2)  º Z4
(x3,x1)  º Z3
Z7+  º (x4,x2)
(x4,x2)  º Z7
(x4,x3)  º Z5
Z8+  º (x4,x1)
(x4,x2)  º Z7
(x4,x1)  º Z8

No comments:

Post a Comment