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
ecognizes the language L = {0
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