= = = 3. (5 pts) Consider the product construction of automata. Given Ai (Qi,, Si,...

Transcribed Image Text:

= = = 3. (5 pts) Consider the product construction of automata. Given Ai (Qi,, Si, q, Fi) (i 1,2) two complete deterministic finite state automata, define the product automaton A A1A2 = (Q, , 8, 90, F) such that Q = Q1Q2, the transitions satisfy: ((91, 92), a, (91, 92)) 8 if and only if (q1, a, q) 81 and (92, a, 92) 82 and 90 = (90, 9). Prove that = (a) F Fx F2 implies L(A) = L(A1) L(A2) and (b) F Fx Q2 UQ1 x F2 implies L(A) = L(A) UL(A2). = = = = 3. (5 pts) Consider the product construction of automata. Given Ai (Qi,, Si, q, Fi) (i 1,2) two complete deterministic finite state automata, define the product automaton A A1A2 = (Q, , 8, 90, F) such that Q = Q1Q2, the transitions satisfy: ((91, 92), a, (91, 92)) 8 if and only if (q1, a, q) 81 and (92, a, 92) 82 and 90 = (90, 9). Prove that = (a) F Fx F2 implies L(A) = L(A1) L(A2) and (b) F Fx Q2 UQ1 x F2 implies L(A) = L(A) UL(A2). =