0. Read product construction from textbook.
================ Part-A ==================
1. Prove the correctness of your construction in HQ2 using extended transition function. Do not use the original definition of "acceptance by DFA". You may need to prove additional properties of d'.
2*. Given a DFA D, construct an NFA N such that L(N) = { reverse(w) : w belongs to L(D) }. Prove correctness of your construction. Can you prove using the extended transition function (you may need to prove additional properties of that function)?
================ Part-B ==================
Construct DFAs for these languages and prove that they are correct. Try to write down the level-1 proofs.
3. All strings in which the number of 0s is even and the number of 1s is not divisible by 3.
4. All strings in which the number of 0s is even or the number of 1s is not divisible by 3.
5. All strings that are both the binary representation of an integer divisible by 3 and the ternary (base-3) representation of an integer divisible by 4. For example, the string 001100 is an element of this language
*4. All strings whose length satisfies (|x| choose 2) = 2 (mod 6). You can use the fact that (n+1 choose 2) = (n choose 2) + n.
*5. All strings in which 010 appears exactly once.