Summer 2018 -Midterm #3 TMs, D, and SD Each T/F question is worth 2 points. T (F

Question

Summer 2018 -Midterm #3 TMs, D, and SD Each T/F question is worth 2 points. T (F) 1. If L E D then L SD T F 3. If a TM semidecides a language L, it will not necessarily accept w E L. TF 4. If a TM semidecides a language L, it will not necessarily reject w e L T F 5. If L e SD/D then -L SD. T F 6. If L E SD then its possible that -L e CFLS. TF 7. TMšs are a formalism for expressing the intuitive concept of a computational algorithm. T F 8. H = { : M halts on w), and MH is a TM that accepts H M1() will halt if MH accepts(), and Mi() will loo otherwise. M1() must loop. T F 9. Given a string w and a language L, a Universal TM can decide if w e L. T 10. At every step in a computation, a TM writes a symbol from 2 on the F T F TF tape, and moves one square to the left or right. 11. 12. 13. A TM's configuration consists of its current state, the position of its For any TM, M is a TM with input alphabet ? and tape alphabet. ?. ?. read/write head, and the active tape. T F 14, L ={ : M re-enters its start state). Rice's theorem could be used to prove that L D F 15. L = { : M re-enters its start state). Le SD/D. F 16. L = { : For M, I?1 = izi + 1). Le SD/D. F 17, L = { w : w ends with a b). L E SD/D. F 18, L = { : L(M) = {b). Le SD/ D. F Rice's theorem could be used to 19, prove that LgD. L = { : L(M) e CFLs). 20. L = { : IL(M)[

Explanation / Answer

7) True

9) False

10) True

11) False ( Tape can contain blank symbol also)

12) True

13) True

17) True

18) True

21) True (Turing enumerable).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.