Project #1 FAQ

Question: Can I use my one 48-hour extension on a project?
Answer: Yes.

Question: I need a hint to get started.
Answer: Nathan Folkert offers some Project Hints. Jeff Ullman offers More Hints. Curiously, these two documents, written independently, cover essentially different aspects of the problem.

Question: Is project #1 part 1 of 3 phases or all 3 phases? According to the handout, it seems only Part 1 is due on Feb 2.
Answer: That's correct. The only thing due next Wednesday (feb 2) is a function that takes a regular expression and (using our parser if you want), returns an NFA or DFA in the form of a transition table.

Question: Can we use C++ and STL on this assignment? I really don't want to waste time writing a dynamically sizing array, etc.
Answer: Yes, using C++ is fine. You'll need to include a makefile or other straightforward directions for compilation, and it needs to result in the same functionality as we expect -- in other words, we want you (for Part 1, due on Feb 2) to construct a DFA or NFA from a regular expression, using our parser if you want. This assignment is not about writing dynamic arrays, so if you'd like to use them but don't want to implement them, then go ahead and use C++ or existing library code. The main point of this assignment is in the conversion algorithms and attempting to design an efficient representation for NFAs and DFAs.

Question: Do we have to handle any RE or FA, no matter how large.
Answer: Given that computer address spaces are limited, there is no way you could do that. The typical computer has an address space of about 4 billion bytes, so you should be able to handle at least a million states, maybe more if you are clever.

Question: You never covered ways to translate the ? or superscript + operators into epsilon-NFA's.
Answer: Since they are equivalent to expressions using the union, dot, and star operators, there is certainly some way to do the translation to an epsilon-NFA. However, if you are clever, you can come up with two modifications of the construction for star that serves for ? and superscript-+.

Question: Is it OK just to turn everything into an NFA, or even leave it as an epsilon-NFA?
Answer: While some people have interpreted the problem as allowing such a solution, it will be inefficient when we try to search large files for occurrences of a pattern matching even a simple regular expression. Thus, we will not give full credit for something that doesn't create a DFA when the number of states is modest (we'll leave to you what an appropriate limit is). Moreover, in project 3, you will find your solution too inefficient to do anything useful (probably).