Computer Science 466/656: Automata and Formal Languages
Spring 2001
Homework Assignment 9.
Due Wednesday, April 18, 2001
You may discuss this assignment with other students in the class, or other
persons. But you must actually write the assignment in your own hand.
You must turn in the homework on letter-sized paper, with your name at the
top of each page. Use pen or pencil, any color.
Do not type your homework, and do
not write your homework as a computer file and turn
in a printout.
-
Work problem 11.1(a,b) on page 330 of your textbook.
-
Work problem 11.3(a,c) on page 330 of your textbook.
-
Work problem 12.7 on page 361 of your textbook.
-
Work problem 12.14 on page 361 of your textbook. But, do not give
the proofs, just the answers, together with an explanation that
is at most one line long, such as,
"because I think that I can find a reduction of
the diagonal language to it," or even more vaguely, like,
"because it looks similar to example X on page Y of the textbook."

Back to
Course Page