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

#### Problems

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

• 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 4:30 pm on Friday, November 1st:
• by submitting an electronic version of your solutions using the turnin system as explain above.
• by handing in your solutions during class on Friday, November 1st.
• by handing in your solutions during Beth's office hour on Friday, November 1st, 12-1 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).