COT-5310 Theory of Computation IAssignment 5Florida International UniversityKnight Foundation School of Computing and Information Sciences1. (10 points) Formally prove that the necessary and...

Questions was attached.


COT-5310 Theory of Computation I Assignment 5 Florida International University Knight Foundation School of Computing and Information Sciences 1. (10 points) Formally prove that the necessary and sufficient condition for decidability of a language is that there must be a TM that enumerates its elements in shortlex order1. 2. (10 points) Provide a behavioral-level description of a multi-tap TM that computes the function f : 1n 7→ 1log∗(n) for every n ∈ Z≥0 where: log∗(x) = { 0 if x ≤ 1; 1 + log∗(log2(x)) if x > 1. 3. (10 points) Let INFINITEDFA = {⟨A⟩|A is a DFA and L(A) is an infinite language}. Show that INFINITEDFA is decidable. 4. (10 points) Let INFINITEPDA = {⟨P ⟩|P is a PDA and L(P ) is an infinite language}. Show that INFINITEPDA is decidable. 5. (10 points) LetA = {⟨R, S⟩|R and S are regular expressions and L(R) ⊆ L(S)}. Show that A is decidable. 6. (10 points) Let EQUIVNDFA = {⟨N,D⟩|N is a NFA and D is an DFA equivalent to N}. Show that EQUIVNDFA is decidable. 7. (20 points) Let A and B be two disjoint languages. Say that language C separates A and B if A ⊆ C and B ⊆ C. Show that any two disjoint Turing co-recognizable languages are separable by some decidable language (Hint: construct a decider for C). 8. (20 points) Use proof by construction to show that the following language is Turing co-recognizable: SIZETM = {⟨M,n⟩|M is a TM and |L(M)| ≤ n and n ∈ Z+}. 1Shortlex order is defined in Chapter 0 of the textbook. 1 COT-5310 Theory of Computation I Assignment 5 Florida International University Knight Foundation School of Computing and Information Sciences 1. (10 points) Formally prove that the necessary and sufficient condition for decidability of a language is that there must be a TM that enumerates its elements in shortlex order1. 2. (10 points) Provide a behavioral-level description of a multi-tap TM that computes the function f : 1n 7→ 1log∗(n) for every n ∈ Z≥0 where: log∗(x) = { 0 if x ≤ 1; 1 + log∗(log2(x)) if x > 1. 3. (10 points) Let INFINITEDFA = {⟨A⟩|A is a DFA and L(A) is an infinite language}. Show that INFINITEDFA is decidable. 4. (10 points) Let INFINITEPDA = {⟨P ⟩|P is a PDA and L(P ) is an infinite language}. Show that INFINITEPDA is decidable. 5. (10 points) LetA = {⟨R, S⟩|R and S are regular expressions and L(R) ⊆ L(S)}. Show that A is decidable. 6. (10 points) Let EQUIVNDFA = {⟨N,D⟩|N is a NFA and D is an DFA equivalent to N}. Show that EQUIVNDFA is decidable. 7. (20 points) Let A and B be two disjoint languages. Say that language C separates A and B if A ⊆ C and B ⊆ C. Show that any two disjoint Turing co-recognizable languages are separable by some decidable language (Hint: construct a decider for C). 8. (20 points) Use proof by construction to show that the following language is Turing co-recognizable: SIZETM = {⟨M,n⟩|M is a TM and |L(M)| ≤ n and n ∈ Z+}. 1Shortlex order is defined in Chapter 0 of the textbook. 1