Question 1. [20 marks]
Term Test # 1 (Duration: 50 minutes)
Design a single-tape deterministic TM that given an input w ends up with w ⊔ w on the tape with the head pointing to the leftmost character. Assume the input alphabet is Σ = {0, 1}. You should also provide a high level description of your TM in words.
Question 2. [20 marks]
Let T = {⟨M⟩ | M is a TM with |L(M)| = 5}. Does T ∈ SD? Does T ∈ coSD? Justify your answers.
(You can assume the input alphabet is Σ = {0, 1}.)
Page 2 of 2 Total Marks = 40 End of Term Test #1 (Duration: 50 minutes)