===========================================================================
CSC 363                     Homework Exercise 1                 Winter 2008
===========================================================================

Due: by 6pm on Wed 16 Jan
Worth: 1.5%


1.  Give an example of a Turing Machine that never halts (i.e. for all
    inputs, the TM never enters its accepting or rejecting state), a
    separate example of a Turing Machine that always accepts (i.e., the TM
    accepts every input), and a separate example of a Turing Machine that
    always rejects (i.e., the TM rejects every input).  Give formal
    descriptions for all your TMs.


2.  Let M be the TM with input alphabet \Sigma = {a, b}, tape alphabet
    \Gamma = {a, b, _}, and transition function given by the following
    table (where q_0 is the initial state, q_A is the accepting state, q_R
    is the rejecting state, and square brackets [] have been put around
    "superfluous" transitions -- transitions that will never be encountered
    because of the design of the TM, and that are specified only for the
    sake of completeness):

                    a           b           _

         q_0:    q_1,_,R     q_4,_,R     q_A,_,R

         q_1:    q_2,a,R     q_2,b,R     q_R,_,R

         q_2:    q_2,a,R     q_2,b,R     q_3,_,L

         q_3:    q_7,_,L     q_R,_,L    [q_3,_,L]

         q_4:    q_5,a,R     q_5,b,R     q_R,_,R

         q_5:    q_5,a,R     q_5,b,R     q_6,_,L

         q_6:    q_R,_,L     q_7,_,L    [q_6,_,L]

         q_7:    q_7,a,L     q_7,b,L     q_0,_,R

    Give the sequence of configurations in the computation of M on each
    input string below.

    (a) \epsilon (the empty string)
    (b) a
    (c) aa
    (d) aba
    (e) abbbaba


3.  Let M be a Turing Machine with accepting state q_A and rejecting
    state q_R, and let M' be a Turing Machine identical to M except that
    q_R is the *accepting* state of M' and q_A is the *rejecting* state of
    M'.  Recall that the language recognized by M is defined as L(M) =
    { w (- \Sigma* : M accepts input string w }, i.e., for all input
    strings w (- \Sigma*, w (- L(M) if M accepts w, and w !(- L(M) if M
    rejects w or M loops on w.

    (a) What can you say about L(M'), the language recognized by M',
        compared to L(M), the language recognized by M?

    (b) If M always halts (i.e., M either accepts or rejects for every
        input, or equivalently, M never loops on any input), can you say
        that M' always halt?

    (c) If M always halts, what is the relationship between L(M) and L(M')?