Project #1 FAQ
Can I use my one 48-hour extension on a project?
I need a hint to get started.
Nathan Folkert offers some Project Hints.
Jeff Ullman offers More Hints.
Curiously, these two documents, written independently, cover essentially
different aspects of the problem.
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.
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.
Can we use C++ and STL on this assignment? I really don't want to waste
time writing a dynamically sizing array, etc.
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.
Do we have to handle any RE or FA, no matter how large.
Given that computer address spaces are limited, there is no way you could
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
You never covered ways to translate the ? or superscript + operators into
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-+.
Is it OK just to turn everything into an NFA, or even leave it as
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
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).