COT-5310 Theory of Computation IAssignment 4Florida International UniversityKnight Foundation School of Computing and Information Sciences1. (15 points) Assume that A = {anbmck|n,m, k ∈ Z≥0, n...

There is file that I was attached to this question.


COT-5310 Theory of Computation I Assignment 4 Florida International University Knight Foundation School of Computing and Information Sciences 1. (15 points) Assume that A = {anbmck|n,m, k ∈ Z≥0, n = 2m} and B = {anbmck|n,m, k ∈ Z≥0,m = 2k} are two CF languages. (a) (10 points) Use A and B to prove that the family of context-free languages are not closed under intersection (Hint: show that A∩B is not a CFL using pumping lemma for context-free languages). (b) (5 points) Use the proven claim in part a to show that the family of context-free languages are not closed under complement. 2. (15 points) Prove that {anbm2cn2dm|n,m ∈ Z≥0} is not context-free. 3. (35 points) Considering the following state diagram representing a Turing machine, answer to following questions: (a) (10 points) Assuming that Σ = {0, 1}, specify the tuple representing this TM (including the transition function). (b) (10 points) Show the computation process of this TM on the input 0111 as a sequence of instantaneous configurations. (c) (10 points) Is there an input string in which the TM does not halt? If yes, show an example; otherwise, formally prove that for every input string, the TM halts. (d) (5 points) Specify the language recognized by the TM. 1 4. (25 points) Provide an implementation-level description (state-diagram) of TM that recognizes the language L = {0b m+n 2 c1m2n|m,n ∈ Z≥0}. 5. (10 points) Prove that decidable languages are closed under concatenation, comple- ment, union, and intersection operations. 2