Lab #1: Simulating a DFA


Assigned: Mon 16 Sep 2002

Due: Mon 30 Sep 2002


Description

For this project you should write a program which simulates the computation performed by a deterministic finite automaton. The program should be parameterized (or modular) with respect to the actual DFA simulated; i.e., it should be possible for you to configure the program with the description of particular DFA and then run that DFA on several inputs.

In particular, your program should be able to:

  • simulate a run of the DFA for several successive input strings (without re-reading the DFA description or re-configuring the simulator);
  • reject ill-formed DFA descriptions (see below);
  • determine and report whether or not the DFA accepts a given input string;
  • optionally, output a trace of the computation performed by the machine (e.g., a list of the states entered, in order).

For more details, see the various sections below.

Logistics

As usual, you may use any language or platform you wish for your implementation; the only restriction is that you be able to demonstrate your program for the instructor, either in lab during regularly scheduled hours, or by advance appointment in some other easily accessible place (e.g., the student research lab, WITS labs, instructor's office, etc.).

You should also have a copy of your program available for inspection at the time of the demo (as usual, I will inspect programs and make verbal comments, but I won't be grading the source code on paper).

Input and configuration

You are responsible for designing an input method for DFAs. It should be possible for you to enter in a DFA at demo time (perhaps allowing for me to switch for a few minutes to another group) a DFA of reasonable size (say, about 5 or 6 states) on the basis of a state diagram or other description of the DFA.

Let's assume that all alphabets will include only printable ASCII characters and that states will be named in some reasonable way (e.g., by letters, numbers or other mult-character identifiers). You may decide to make reasonable restrictions on names and the like (e.g., all states are named "qn" for some numeral n).

In my experience, most groups at Willamette using Java will want to use a GUI front-end to specify their machines, and in fact I have anticipated this with the GUI focus of Lab 0. You may, nevertheless, want to consider an ASCII representation for some or all aspects of your interface (for example, entering individual transition information or for saving DFAs to a file (which can be handy during testing). Should you decide to use ASCII input, you might use a syntax like the following to define a simple DFA, assuming the usual order for the five elements of the tuple: 

	q0, q1
	"abc"
	q0:a->q1, b->q1;  q1:a->q0, b->q0
	q0
	q0, q1
In this syntax, newlines are used to separate parts of the tuple, commas to separate states in sets of states, a traditional string syntax is used for the alphabet and semi-colons are used to separate parts of the specification of the transition function.

Note that the machine described above probably doesn't do anything interesting: it's just an example of a possible input syntax for configuration.

Note also that this is only a sample syntax: for your program, you might use something completely different and, most likely will use a GUI front end. As an example of what a typical GUI might look like in operation, consider the following:

As discussed in class, the obvious way to implement a DFA is to keep track of the current state and input position and to use a table to implement the transition function, looking up new states as you proceed through the input.

Enhancements

Part of the goal of the programming projects in this course is to give you the opportunity to develop some significant programs on your own, in a group setting, with relatively few constraints. This should allow you to exercise both your design and coding skills. In order that you may take best advantage of this opportunity, I will require only that you meet the minimum standards described above, but I am also encouraging you to go beyond the basic problem description and do something more creative, individual and interesting with the general assignment.

For this assignment, one enhancement might be to include the capability to interact with the DFA, i.e., you might print the output "trace" as you go, allowing the user to type the next input character based on this trace information (this would make testing a lot easier).

In any case, no such enhancements are required and you will have the opportunity to earn an "A" in the course even if you only meet the minimum assignment requirements.