===========================================================================
CSC 363                     Homework Exercise 1                   Fall 2008
===========================================================================

Due: by 2pm on Wed 17 Sep
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.  Let M be the TM with input alphabet \Sigma = {a,b}, tape alphabet
    \Gamma = {a,b,x,_}, and transition function given by the following
    table (where q_0 is the initial state, q_A is the accepting state, and
    q_R is the rejecting state):

                    a           b           x           _

         q_0:    q_1,_,R     q_3,_,R     q_0,_,R     q_A,_,L

         q_1:    q_1,a,R     q_2,x,R     q_1,x,R     q_R,_,L

         q_2:    q_2,a,R     q_5,x,L     q_2,x,R     q_R,_,L

         q_3:    q_2,x,R     q_4,x,R     q_3,x,R     q_A,_,L

         q_4:    q_5,x,L     q_4,b,R     q_4,x,R     q_A,_,L

         q_5:    q_5,a,L     q_5,b,L     q_5,x,L     q_0,_,R

    Give the sequence of configurations in the computation of M on each of
    the following input strings.

    (a) \epsilon (the empty string)
    (b) a
    (c) bab
    (d) baabb


2.  Design a TM that adds 1 in base three, i.e., your TM will have input
    alphabet \Sigma = {0,1,2} and on input w (- \Sigma*, your TM will
    produce output w' (- \Sigma*, where w' represents the number one
    greater than the number represented by w, in base three.  To simplify
    your solution, please use the "alternate convention" mentioned in
    class.

    More precisely, when started in configuration

        _  q_0  d_n d_{n-1} ... d_1 d_0

    where n (- N and d_i (- {0,1,2} for i (- {0,...,n}, your TM will halt
    in configuration

        _  q_A  d'_n' d'_{n'-1} ... d'_1 d'_0

    where n' = n or n' = n+1, d'_i (- {0,1,2} for i (- {0,...,n'}, and

        d'_n' 3^n' + d'_{n'-1} 3^{n'-1} + ... + d'_1 3 + d'_0
        = d_n 3^n + d_{n-1} 3^{n-1} + ... + d_1 3 + d_0 + 1

    For example, the following table lists the final configuration desired
    for a sample of initial configurations.

        Initial configuration      Final configuration
          _ q_0 _                    _ q_A 1
          _ q_0 22                   _ q_A 100
          _ q_0 0121                 _ q_A 0122
          _ q_0 12012                _ q_A 12020

    Give a high-level description (the main idea in one paragraph), an
    implementation-level description (a numbered list that describes
    details of head movements and tape contents, but does not mention
    states), and a formal-level description (full transition table or
    transition diagram) of your TM.  Make sure to relate your formal-level
    description to the equivalent stages in the implementation-level
    description.

    /Hint/:  Your computation should proceed in two distinct phases: first,
    add 1 and propagate the carry; second, insert a new 1 to the left of
    the existing string, if necessary.


3.  BONUS!
    What is the language recognized by the TM from Question 1?