CSC 456/656 Assignment 1
Due date: Thursday, February 3, 2005, 11:30 AM.
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
-
Work Exercise 1.1 and 1.2 on on page 83 of your textbook.
(These should be easy, but you should do them before you do 1.4.)
-
Work Exercise 1.3 on page 84 of your textbook.
-
Work Exercise 1.4 on page 84 of your textbook.
In every case, you should try to find the DFA that has the
smallest possible number of states.
(These will take substantial time, hence you should get started over
the weekend.)
-
For discussion only.
Think of the poor grader
trying to grade Exercise 1.4. Do you think
the "grader's problem" for Exercise 1.4 is decidable or undecidable?
In other words, does there exist a program where Doina could just enter
every answer and the program would output "Right" or "Wrong"?
Do not hand in an answer to this problem, but think about it:
we will discuss it in class.
In reality, On a test, I will mark your answer wrong, even if it's right,
if it's unreasonably complicated, or if I cannot figure out whether it's
right or wrong in a reasonable amount of time. (This is part of the
"communication skills" part of the class.)
Back to
Course Page