WPI Worcester Polytechnic Institute

Computer Science Department

CS4123 Theory of Computation 
Homework 1 - B 2002

By Beth Donovan and Carolina Ruiz 

Due Date: Friday, November 1st at 4:30pm.  
Help session: Thursday, Oct. 31st from 3 to 6 pm (Prof. Ruiz, Beth, and Adam). CS Annex



  1. (10 points) Problem 3.5 from the textbook (page 148).

  2. (10 points) Problem 3.19 from textbook (page 149).

  3. (35 points) Let Sigma = {0,1,#}. Consider the following language over Sigma:

    L = { wwR |  w is a word in Sigma*, wR denotes the reverse of the word w, and the number of occurrences of '#' in wwR is a multiple of 4}

    Assume that 0 is a multiple of 4.

    1. (10 points) Write a algorithm (in pseudo-code) to decide this language L. Your pseudo-code should be detailed enough to be directly implementable on a Turing machine.

    2. (10 points) Construct a state-transitions diagram for a Turing machine that implements your pseudo-code. Remember to make all the transitions explicit in your diagram.

    3. (15 points) Write a computer program that implements your pseudo-code. Write this program using your favorite high level programming language (C, C++, Java, Lisp, or Prolog). Your program should read as input a string and output "accepted" if the input string belongs to the language L and "rejected" otherwise.
      Note: your computer program should be a faithful implementation of your pseudo-code. That is, process the string character by character as a Turing machine would (except for reading in the input and outputting the answer, for which you can use standard input/output string functions in the programming language you choose) .

      Turn in as part of your homework solutions:

      • A printout of your code. Also, submit your code using TURNIN as explain below in the "HOMEWORK SUBMISSION" section.
      • Run your program on each of the following input words. Include a printout of the output of your code on each of these words:
        1. "0111#1##1#1110"
        2. "" that is, the empty word
        3. "00##11##00000##11##00"
        4. "010##11100##00111##010"
        5. "1100###010#11#010###0011"
        Also, submit an electronic copy of this transcript using TURNIN as explain below in the "HOMEWORK SUBMISSION" section.

  4. (25 points) Let Sigma = {x,y,z}. Consider the language

    L = { zkxmyn | k is a multiple of 2, m = 2k, and n = k-1}

    Assume that 0 is NOT a multiple of 2.
    Show that L is decidable by providing a detailed algorithm (in pseudo-code) to decide this language. 

  5. (20 points) [Taken from Moret, 1998] A 2-dimensional Turing machine is equipped with a 2-dimensional tape rather that a 1-dimensional tape.  The 2-dimensional tape is an unbounded grid of tape squares over which the machine's head can move in 4 directions: left, right, up and down.  The head of the Turing machine starts in the upper left hand corner, and is governed by two restricts: 1. the head can never move up when in the top row, and 2. the head can never move left when in the first row.  A picture of this tape is shown below:

The 2-D tape for the 2-D Turing machine

A 2-dimensional (2-D) Turing machine is defined, formally, in the same way a conventional Turing machine is defined, with the exception of delta.  That is: Q={q0, ..., qn, qaccept, qreject}; Sigma is the input alphabet; Gamma is the set Sigma union 'blank'.  The change to delta is the following:

delta: Q x Gamma ->Q x Gamma x {L, R, U, D}.

Show that this variant Turing machine model is equivalent to the ordinary Turing machine model.

Homework Submission

Additional Problems for Students taking the course for Graduate Credit

  1. (10 points) Problem 3.13 from textbook (page 149).

  2. (10 points) Prove that every finite language is decidable.