Homework Exercise 1

Due: by 2pm on Web 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 Σ = {a,b}, tape alphabet Γ = {a,b,x,_}, and transition function given by the following table (where q0 is the initial state, qA is the accepting state, qR is the rejecting state):

    a b x _
    q0 q1,_,R q3,_,R q0,_,R qA,_,L
    q1 q1,a,R q2,x,R q1,x,R qR,_,L
    q2 q2,a,R q5,x,L q2,x,R qR,_,L
    q3 q2,x,R q4,x,R q3,x,R qA,_,L
    q4 q5,x,L q4,b,R q4,x,R qA,_,L
    q5 q5,a,L q5,b,L q5,x,L q0,_,R

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

    1. ε (the empty string)
    2. a
    3. bab
    4. baabb

  2. Design a TM that adds 1 in base three, i.e., your TM will have input alphabet Σ = {0,1,2} and on input w ∈ Σ*, your TM will produce output w' ∈ Σ* 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

    _  q0  dn dn-1 ... d1 d0

    where n ∈ N and di ∈ {0,1,2} for i ∈ {0,...,n}, your TM will halt in configuration

    _  qA  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' 3n' + d'n'-1 3n'-1 + ... + d'1 3 + d'0
    = dn 3n + dn-1 3n-1 + ... + d1 3 + d0 + 1

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

    Initial configuration Final configuration
    _ q0 _ _ qA 1
    _ q0 22 _ qA 100
    _ q0 0121 _ qA 0122
    _ q0 12012 _ qA 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?