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