WPI Worcester Polytechnic Institute

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

CS4123 Theory of Computation 
Homework 1 - D 2002

PROF. CAROLINA RUIZ 

Due Date: Tuesday, March 26th at 5 pm. 
Help session: Monday, March 25th, 1-2 pm Room: AK219

------------------------------------------

Problems

  1. (10 points) Exercise 3.6 from textbook (page 148).

  2. (20 points) Problem 3.14 from textbook (page 149).

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

    L = { anbncn | n is a multiple of 3}

    where an denotes "a" repeated n times. Assume that 0 is not a multiple of 3.

    1. (6 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. (7 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. (7 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 outputing 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. "aaaabbbbcccc"
        2. "" that is, the empty word
        3. "aaabbbcccaaabbbccc"
        4. "aaabbbbbbccc"
        5. "aaaaaaaaaaaabbbbbbbbbbbbcccccccccccc"
        Also, submit an electronic copy of this transcript using TURNIN as explain below in the "HOMEWORK SUBMISSION" section.

  4. (10 points) Let Sigma = {a,b}. Consider the language

    L = { ww | w is a word in Sigma*}

    Note that "aabaab" belongs to L, but "abaaab" does not. Show that L is decidable by providing a detailed algorithm (in pseudo-code) to decide this language.
    Hint: Construct a 2-tape non-deterministic Turing machine that decides this language and then explain why there must be a regular (single-tape, deterministic) Turing machine that decides this language.

  5. (15 points) Problem 3.10 from textbook (page 148).

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.