### 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

• Code and Execution transcript: Submit the following files using the turnin program. The name is the assignment under which you should submit is hw1.

• hw1_prb3.[lastname] containing the program that you wrote to implement your pseudo-code. The lastname/extension of this file will depend on the programming language you used (eg. it'll be hw1_prb3.c if you wrote your program in C).
Remember to document your project as much as you can so that we know how to compile, run, and use your program.

• hw1_prb3.transcript containing the results of running your program over the test cases provided.

• Written part: You can submit the rest of the homework assignment in any of the following ways. Make sure you hand it in BY 5 pm on Tuesday, March 25th:
• by submitting an electronic version of your solutions using the turnin system as explain above.
• by handing in your solutions during class on Tuesday, March 26th.
• by handing in your solutions during John's office hour on Tuesday, March 26th, 4-5 pm.
• by leaving your solutions in my mailbox (CS office FL233). PLEASE MAKE SURE YOU LEAVE YOUR SOLUTIONS IN **MY** MAILBOX (the one UNDER the arrow marked with my lastname RUIZ).

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

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