• Site Map

• Lectures

• Homework

• Tests/Exam

• Main Webpage

Homework Exercise 4

Due: by 2pm on Web 22 Oct
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

1. Give a detailed proof that if A ≤_m B and B ≤_m C, then A ≤_m C, for all languages A,B,C.

2. Prove that L ≤_m A_TM, for all recognizable languages L.

3. Prove or disprove: If A ≤_m B and B is regular, then A is regular.