Programming Project
(Due: 3/30/05 Wednesday, points 50)

Write a program that accepts an input set of strings on lower case English Alphabet
and create a Non-deterministic Finite Automaton for accepting only that set.

Extend the program to create a corresponding Deterministic Finite Automaton
corresponding to the NFA from the first phase.

Submission: well-documented source code, sample runs (in hard copy), possible
demo.

----- clarifying mail responses -------
> Hello,
> I have a couple questions/concerns.
> I was wondering if you could clarify some expectations
> for the project.  My current implementation does a
> minimization on the input to ensure words starting
> with the same letters do not generate repeat nodes,
> and likewise minimizes duplications of postfix
> portions of words that are the same.  However, in
> doing this minimization the NFA internal storage
> structures needed are really only that of essentially
> a DFA.  Technically this meets the requirements of the

I am not sure what exactly you mean by this. NFA (possibly NFA-e) is the easiest way to handle this. And I expect the output from phase 1 to be an NFA (could have been nfa-e, but since I did not say that in the project description I will expect just an NFA). If your scheme creates DFA in the first phase I cannot penalize you, but I would like to see an easy NFA. However, the second phase must be able to convert arbitrary NFA to a corresponding equivalent DFA. 

> project, but I am curious as to whether it would be
> accepted as being in the spirit of the project.
> Additionally what type of data are you looking for in
> the write up?  Did you want to see performance data or
> time analysis?  Perhaps a high level design
> description?
> 
People get creative in experiment design and reportage. So, I do not want be restrictive there. Yes, I want gigh level description, some input output runs, and source code to ensure that it really is what the description says.

> Additionally for the final you mentioned something
> about using the slides during the midterm?  So for
> clarification, the book is not allowed, notes are not
> allowed, but a clean hard copy of the class slides is
> allowed?
The text book is allowed, the slides without any notes on it are allowed, but nothing else.
------------------

There are two types of input. Firstly, the finite set of strings on which
the machine is to be built, e.g., {ab, abd, d, adc}, not regular 
expressions. Subsequently, your machine should run on a string (e.g., 
abc) and output "accept" or "reject."

Intermediate phase of the project should output a transition function on a
file.
  
DM

On Sun, 27 Mar 2005, George Frederick wrote:

> I have some questions regarding the program we're to write for FLAT. 
> Namely, what are the inputs and outputs supposed to look like? Is the
> input to be a regular expression? Is the output supposed to be a
> transition table? Thanks for your time.
>
> -George Frederick
>
---------------------------