CSC 463H1 Test Exan
Question 1. [20 marks]
Term Test # 1 (Duration: 50 minutes)
Copyright By PowCoder代写 加微信 powcoder
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)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com