WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4123 Theory of Computation 
Homework 1 - B 2004

Due Date: Friday, November 5th at 12:00 noon.
NO SUBMISSIONS WILL BE ACCEPTED AFTER 12:05 PM.
 
------------------------------------------

Problems

  1. (10 points) Problem 3.1 from the textbook (page 147).

  2. (15 points) Let Sigma = {a,b}. Provide the pseudo-code description as well as the state-diagram of a Turing Machine that decides the following language:

    L1 = { w |  w is a word in Sigma* that contains an odd number of a's in a row}.

    As an illustration, your TM should accept the words "aabbbaaaaab"and "bbabaa"; and should reject "bbaaaaaabaab" and "" (the empty word).

  3. (35 points) Let Sigma = {a,b,c}. Consider the following language over Sigma:

    L2 = { aibjck |  k is the integer division of i by j (that is, k = i div j)}.

    As an illustration, the word "aabbb" belongs to the language because 2 div 3 is 0; the word "aaaaaaaaaabbbbcc" belongs to the language because 10 div 4 is 2; the word "bbb" belongs to the language because 0 div 3 is 0; the word "aaaabbbbcc" does not belong to the language because 4 div 4 is not 2; the word "ababc" does not belong to the language because it is not of the form aibjck; and words with 0 occurrences of "b" are not in the language as division by 0 is not allowed.

    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. See notes below). Your program should read as input a string and output "accepted" if the input string belongs to the language L and "rejected" otherwise.
      Notes:
      • 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) .
      • If at all possible, re-use the appropriate parts of the code written by John Shutt and provided as solution of homework1 in D-term 2002.

        Submit as part of your homework solutions:

        • A printout of your code. Also, submit your code using MyWPI 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. "aabbb"
          2. "" that is, the empty word
          3. "aaaaaaaaaabbbbcc"
          4. "bbb"
          5. "aaaabbbbcc"
          6. "ababc"
          Also, submit an electronic copy of this transcript using myWPI as explain below in the "HOMEWORK SUBMISSION" section.

  • (20 points) Let Sigma = {x,y}. Consider the language

    L3 = {w | w is a word in Sigma* that contains twice as many x's as y's, OR twice as many y's as x's}.

    As an illustration, "yxxyyyyyx", "yxyxxx", and "" (the empty word) belong to the language, but "x", "yx", "xyxyy" do not.

    Show that L is decidable by providing a detailed algorithm (in pseudo-code) to decide this language. 
    Hint: Construct a non-deterministic Turing machine that decides this language and then explain why there must exist a deterministic Turing machine that decides this language.

  • (20 points) A Left-Right-Stay Turing machine is similar to an ordinary Turing machine except that its head can move Left (L), Right (R), or Stay put (S). In other words, its transition function is defined as:
    delta': Q' x Gamma' -> Q' x Gamma' x {L,R,S},
    where S means that the head does not move.
    Prove that this variant of Turing machines is equivalent to the ordinary Turing machines. Prove this in two steps:

    1. (5 points) Given any ordinary Turing machine M = [Q,Sigma,Gamma,Delta,q0,qaccept,qreject], construct a Left-Right-Stay Turing machine T = [Q',Sigma',Gamma',Delta',q'0,q'accept,q'reject] that simulates M. You need to stay explicitly how to obtain Q' from Q, Sigma' from Sigma, etc.

    2. (15 points) Given any Left-Right-Stay Turing machine T = [Q',Sigma',Gamma',Delta',q'0,q'accept,q'reject], construct an ordinary Turing machine M = [Q,Sigma,Gamma,Delta,q0,qaccept,qreject] that simulates T. You need to stay explicitly how to obtain Q from Q', Sigma from Sigma', etc.

    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) Problem 3.17 from textbook (page 149).