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
- (10 points) Problem 3.5 from the textbook (page 148).
- (10 points) Problem 3.19 from textbook (page 149).
- (35 points) Let Sigma = {0,1,#}. Consider the following language
over Sigma:
L = { ww^{R} | w is a word in Sigma*, w^{R}
denotes the reverse of the word w, and the number of
occurrences of '#' in ww^{R} is a multiple of 4}
Assume that 0 is a multiple of 4.
- (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.
- (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.
- (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:
- "0111#1##1#1110"
- "" that is, the empty word
- "00##11##00000##11##00"
- "010##11100##00111##010"
- "1100###010#11#010###0011"
Also, submit an electronic copy of this transcript using TURNIN
as explain below in the "HOMEWORK SUBMISSION" section.
- (25 points) Let Sigma = {x,y,z}. Consider the language
L = { z^{k}x^{m}y^{n} | 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.
- (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={q_{0}, ..., q_{n}, q_{accept}, q_{reject}}; 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).
Additional Problems for Students taking the course for Graduate Credit
- (10 points) Problem 3.13 from textbook (page 149).
- (10 points) Prove that every finite language is decidable.