CSCC63, Winter 2019 Assignment # 2
Due: Friday February 22 at 11:59 pm
You may work with a single partner. If you do work with a partner, please list both of your names on your assignment. You are not allowed to discuss the assignment with anyone other than your partner, the TAs, and the instructor.
In this assignment, we will use the following definitions:
• A is an arbitrary regular language such that A and A are both infinite.
Can you see why this must be decidable? You may use MA as a decider for it.
• B is the language {01101110}.
• C is the language {1}∗.
• Disthelanguage{⟨M⟩|M isaTM suchthatL(M)={1}}.
We discussed this language in lectures 6 and 7.
• f(n)=(n+1)!foralln∈N.
For each of the following languages, prove whether it is decidable, recog- nizable, co-recognizable, or neither. Do not use Rice’s theorem. If you write a TM, briefly explain why it must work. (20 points each)
L1 ={⟨M⟩|M isaTM suchthatA=L(M)}. L2 ={⟨M⟩|M isaTM suchthatB⊆L(M)}. L3 ={⟨M⟩|M isaTM suchthatB=L(M)}. L4 ={⟨M⟩|M isaTM suchthatC⊆L(M)}. L5 ={⟨M⟩|M isaTM suchthatD=L(M)}. L6 ={x|∃y∈D, xy∈A}.
L7 = {⟨M ⟩ | M is a T M that accepts “01101110” within f (10) steps}. L8 = {⟨M⟩ | M is a TM that outputs f(n) for some ⟨n⟩}.
L9 = {⟨M⟩ | M is a TM that outputs f(n) for all ⟨n⟩}.
⟨M⟩|M isaTM which,oninput⟨n⟩, L10 = outputs f(n) whenever it halts within f(n) steps.
1