2. (10 marks) Consider the language
Prove that ALLTM 6m L2.
3. (5 marks) Consider the language
L2 =⟨M,N⟩ L(M)6m L(N) .
CSCC63 Assignment 2
Reductions, Polytime Reductions, and NP Due 11:59pm, July 14
Warning: For this assignment you may work either alone or in pairs. Your electronic submission of a PDF to Crowdmark affirms that this assignment is your own work and that of your partner, and no one else’s, and is also in accordance with the University of Toronto Code of Behaviour on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSCC63. Note that using Google or any other online resource is considered plagiarism.
1. (20 marks) Consider the language
L1 = ⟨G1,G′1⟩ G1 and G′1 are CFGs and no x ∈ L(G1) is a substring of any y ∈ L(G′1) . Is L1 decidable, recognizable, co-recognizable, or neither? Prove your answer.
Fact-Range=⟨n,a,b⟩ n,a,b∈N,and∃k∈N,a6k6bandkdividesn . Now, consider the following program to solve Fact-Range:
Find-Fact= “On ⟨n, a, b⟩:
1. 2. 3. 4. 5. 6.
If(0