1. Design a TM to perform circular left-shift operation. 2. Design a TM to accept the language (0a, 1ab, 2bab 1}. Draw the state-transition diagram, and explain how your TM operates. 3. Let w = 100101 and G be the context-free grammar whose productions are given below (Note that G is in Chomsky Normal Form). 1. S CY 5. YKK 2. S YK 6. Y-0 3. C YC 7. K CY 4. C71 a. Draw a parse tree for w. 8. K1 b. Test membership of w in L(G) using CYK algorithm Write down your solution step by step by giving proper explanations. c. Which nonterminals in G can be used to generate w? 4. Given language L = {0 1 2 3 | i,j 1}. a. Prove that L is context-free. b. For a given language X, let Half(x) = {w| wx e X and [w] = |x|). Prove that Half(L) is not context- free.