INFO4MYSTREY , Best Mark Mystery

Question 01 : Note that L(A) ≠ L(B) if either 1. there is an x Î L(A) Ç L(B) 2. there is an x Î L(B) Ç L(A) In short if (L(A) Ç L(B)) È (L(B) Ç L(A)) = Ǿ then L(A) = L(B) Now, we know that the following properties of regular languages. 1. If P is regular and Q is regular then P È Q is regular. Furthermore, given two DFAs D 1 and D 2 we can construct a DFA such that D such that L(D) = L(D 1 ) È L(D 2 ). 2. If P is regular then P is regular. Furthermore, given a DFA D‟ we can construct a DFA D 0 such that L(D‟) = L(D). Hence we can make a DFA C such that: L(C) = (L(A) Ç L (B)) È (L(B) Ç L (A)) = Ǿ 1. On input <A, B> 2. Construct the DFA C described above. 3. If L(C) = Ǿ accept. Else reject. Question 02: Turing Machine A Turing machine has a input tape which is infinite. Hence, the machine has unlimited memory. It has a read/write tape head which can move left and write and change symbols while the machine is performing its computation. The ...