You have a choice in fulfilling the work for this honors adjunct. You may do either the programming option or the theory option.
Programming Option:
You may work alone, in pairs, perhaps in a larger group.
The goal of this project is to create an interactive, animated demo of the Myhill-Nerode state-minimization algorithm for finite state automata. You must first create an interactive animation of finite-state automata. I can give you the C++ code for my version of this but you probably want to convert it to JAVA.
We will meet up to one hour a week to look over code, to plan the demo, and to discuss the state-minimization algorithm.
You must submit a small user manual for the program.
A DFA interactive animation should be completed by April 25, 2002.
The final project should be ready to demo by May 23, 2002.
Theory Option:
This work is to be completed alone.
You must complete additional problems assigned from the text. The textbook for this course, "Introduction to the Theory of Computation" by Michael Sipser, is intended for undergraduate or graduate courses. It contains a wealth of neat but difficult problems.
We will meet up to one hour a week to discus problems and present solutions.
There are 30 problems listed below. You do not have to do them all. Each correct solution, submitted on time, will receive 1 point. Each half-baked solution, submitted on time, will receive 1/2 point. Late submissions will not be accepted. As with regular homework, your work must be neat and legible or it will not be graded. Here is the grading scale:
| Problem | Hint |
|---|
| 1.19 | Easy |
| 1.20 | Imitate the definition of a DFA, Definition 1.1, page 35. |
| 1.21 | You must do 1.20 correctly before you can do this. |
| 1.25 | Use 1.24 and think about carrying when you add. |
| 1.26 | Same hint as 1.25 but this one is harder.
You may have to carry 1 or 2 when you multiply by 3. |
| 1.27 | Don't use 1.24. Read the numbers from left to right
This one is fairly straight forward.. |
| 1.29 | Easy |
| 1.30 | Don't use 1.24. Read the numbers from left to right.
What is (2*k) mod n in terms of k mod n?
What is (2*k + 1) mod n in terms of k mod n? |
| 1.41 | Build a DFA or NFA to recognize the language D. |