===========================================================================
CSC 363                     Homework Exercise 4                   Fall 2008
===========================================================================

Due: by 2pm on Wed 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.