|
Contest Closed
A deterministic finite automaton (DFA) is a machine that applies a finite number of rules to an input and produces a result. There are many possible kinds of DFAs. One simple kind of automaton takes as input a semi-infinite tape of zeros and ones. The read head starts on the left end of the tape in start state 0. At each step, the DFA reads the symbol (0 or 1) in the cell under the read head. Then depending on its current state, the DFA sets the cell to 0 or 1, enters a new state, and moves left or right.
By definition, the DFA stops when the read head runs off the left end of the tape. In other words, it stops when the read head is on the left end of the tape and then it tries to move left. Remember the tape is semi-infinite so there is no right end.
A state definition includes:
- CurrentStateId
- CurrentCellContents
- NewCellContents
- NewStateId
- MoveLeftOrRight
For example, the following command means:
When in state 9 and you see a 1, change the cell to a 0, move into state 10, and move right.
9, 1, 0, 10, R
For a more interesting example, consider the following program. Remember the DFA begins in the start state 0. The program makes the DFA move to the right as long as it sees a 1. When it finds a 0, the program changes it to a 1 and starts moving back to the left. It continues moving left until it runs off the left end of the tape.
0, 1, 1, 0, R ' Skip a 1 and move right.
0, 0, 1, 1, L ' We found a 0. Change it to a 1 and move left.
1, 1, 1, 1, L ' Keep moving left, leaving 1's unchanged.
Your mission for this contest is to write a simulator for this type of DFA. The program must allow the user to enter a program and tape contents. It should allow the user to save and restore programs and tape contents in disk files. Each command should allow VB-style comments on the right (you're really going to need comments once you start writing non-trivial programs).
The program should then simulate the DFA running the program on the input tape. It should display the DFA's progress graphically as it executes the commands. For example, you might draw a picture of a read head containing across the tape and draw the current state inside the read head. The details are completely up to you!
Obviously you cannot make a tape that is infinitely long since your computer has a finite amount of memory, but you should be able to handle and display at least 100 or so tape cells. You could wrap them across multiple lines, scroll horizontally, draw cells really tiny (e.g. you could use colors to represent 0 and 1 to save space), etc.
Bonus points for things like allowing the user to set breakpoints on tape cells and/or program states, changing the simulation speed, allowing states with textual names, an artistic user interface, etc.
Due Date and Prizes
Please submit your Visual Basic project zipped up using WinZip by November 30, 2002.
I will award books from my current stock to the winners. This project is reasonably straightforward but it is a bit intimidating so I'm giving a relatively late due date. I will also award books to several winners. If you build something reasonably functional, you have a good chance of winning. Those who build the best DFAs get first choice of the books I have available. (I may ask you to chip in for postage if it's going to cost me too much, in case you live on Jupiter or something).
To Think About
The following topics are not part of this contest but as you work with the simulator you might think about them.
There are many other types of automata that may have:
- A read head that can only move right.
- Multiple read heads on a single tape.
- Multiple read heads on multiple tapes.
- A stack where the automaton can read and write items (essentially giving it memory).
There are also non-deterministic finite automata (NFAs). An NFA is allowed to be in more than one state at the same time. Sort of a Zen quantum mechanics sort of thing.
Different models also have different starting and stopping conditions. For example, you could say a DFA accepts the input if it enters a special accepting state. Some models also require the DFA to move to the right end of the input and enter an accepting state to stop.
When you start to write complex programs with the simulator, you may find you wish you had some familiar programming constructs. For example, it might be nice to have a GoSub feature that would let the program jump to a specific state and then return to the original state when the "subroutine" was finished. You may also find places where you could make the code more readable with If statements and loops.
Solutions
Only two solutions were originally submitted before the deadline. Feel free to send me your DFA programs if you like and I will post them here.
Yaron Budowski's DFA allows you to edit the state definitions and tape, and run the simulation. He uses an amazing series of pictures to animate the simulation using BitBlt. This technique demonstrates how to mask an image to overlay one image on another. Very nice!
Version 1 has a bug that makes it save and load tapes incorrectly. Instead of loading 0 and 1, it loads 49 0 and 48 0. This may be a Unicode problem (I use a standard American operating system and I suspect Yaron's is internationalized).
I declared Yaron the winner and awarded him copies of Ready-to-Run Visual Basic Algorithms and Visual Basic Graphics Programming.
Download Version 1.
Download Version 2.
Walter Sung took a less graphical approach, using a text box to display the tape. Unfortunately he also used a LinkedNodeView control for which I don't have a license. This is his own control and he should have a trial version available shortly.
Because so few people submitted something for this contest, I gave Walter a copy of Visual Basic .NET and XML, too.
Download Version 1.
Programs
Yaron's program allows textual names for DFA states so I'll use that notation here.
Increment
The following program moves right until it finds a 0, changes it to a 1, and then moves back to the left off the tape. This increments a single number. For example, if the tape initially holds the unary value 3 (1110000...), the result is 4 (1111000...).
| State | Old Value | New Value | New State | Move | Comment |
|---|
| start | 1 | 1 | start | right | Continue moving right |
| start | 0 | 1 | finished | left | Start moving left |
| finished | 1 | 1 | finished | left | Continue moving left off the tape |
Addition
The following program adds two numbers. It moves right until it finds a 0 and changes it to a 1. It then continues moving right until it finds a 0. It moves back one space and removes the final 1. Then it moves left off the end of the tape. This adds two numbers. For example, if the tape initially holds the unary values 3 and 2 (111011000...), the result is 5 (111110000...).
| State | Old Value | New Value | New State | Move | Comment |
|---|
| start | 1 | 1 | start | right | Moving right to find the gap |
| start | 0 | 1 | skip2 | right | Fill the gap and skip the second number |
| skip2 | 1 | 1 | skip2 | right | Continue skipping the second number |
| skip2 | 0 | 0 | clear1 | left | Move left to remove the last 1 |
| clear1 | 1 | 0 | finished | left | Remove the last 1 and move left |
| finished | 1 | 1 | finished | left | Move left off the tape |
More
Similarly you can build programs to perform more complex operations. For example, you can build programs for multiplication, exponentiation, integer division, and others.
|
