.Theory I - CS 3500 D Spring 2003
Project I (20 points) Due March 17, 2003
You will need to use JFLAP to complete this project. Instructions for obtaining JFLAP are given below.
(2pts) Convert the NFA provided in the file p1.NFA to an equivalent DFA with the smallest possible number of states. Save the result as p1.DFA.
(3pts) Convert the NFA given above and the DFA you obtained from problem 1 to equivalent regular expressions. Export the solutions as p2NFA.RE and p2DFA.RE. Compare these two regular expressions. If they are not the same, explain why.
(5pts) Load and inspect the provided file p3.PDA. What is the language recognized by this pushdown automaton? Write your answer in the format X = {w|w is something}.
(10pts) A Turing machine with stay put instead of left is similar to an ordinary Turing Machine except that the transition function has the form
.
At each point the machine can move its head right or let it stay in the same position. Inspect the Turing machine p4.TM and convert it to an NFA. The NFA should simulate the behavior of the TM. That is, the NFA should have the same states as the TM, and on any input string the NFA should follow the same sequence of states as the TM. (Note: you will have to do this manually). Save the result as p4.NFA.
JFLAP:
You can go to http://www.cs.duke.edu/~rodger/tools/jflaptmp to download JFLAP.
Submission Guidelines:
Written answers should be in text, MS Word, or TeX format in file project1.{txt, doc, tex} and should be submitted to WebCT (=>Homeworks=>Assignments=>Project Part I) along with all your JFLAP files (p1.DFA, p2NFA.RE, p2DFA.RE, and p4.NFA).