Project Assignment 2 - 2006

So about that next project.....I have a language-independent assignment and then a possible extension that is language-dependent. I was stressing about providing the language-dependent piece in both Java and python, but then I looked again at the FOCS project list on sis and it looks to me like we're down to python programmers....If this is so, I won't stress about a Java rewrite of the optional piece as there are plenty of other, language independent options as well. BTW, you may write in any language you choose as long as I can figure out how to run it on my computer....

Basic idea:

Write a FSM simulator that takes an FSM description and a string and simulates the execution of the FSM on the string, printing out each state as it goes.

Notes: In Python and scheme (i.e., in interpreted languages) it's not too to just supply the FSM description and the string as arguments to the appropriate procedures, but in another language (or even in one of those) the FSM description, and, if absolutely necessary, the string, can be hard wired into your program if you really don't want to deal with input parsing. In this case, they should certainly be separate pieces of data so it's easy to try running your program on different FSMs and the same FSM on different strings.

Sample input and the output from my solution (in scheme, 'cause I like it ) is below.

Bells and whistles:

(Choose any, all, or none in order to make the assignment interesting and appropriate given the 2 credit weighting). These are in no particular order and are largely independent of one another:

Handle nondeterministic as well as deterministic automata.
Automagically transform NFAs into DFAs.
Produce some sort of graphical depiction of your FSM in operation
Accept the FSM in the xml format output by JFLAP's GUI
Read in the string one keystroke at a time, i.e., allow user input to drive your FSM.
Couple your FSM interpreter with a sprite animation, i.e., a little animation that changes the actual images shown based on its input. Sean wrote the guts of one that works with JFLAP (shows a character moving to the left, right, up, or down, depending on input); details (soon to be) on the wiki, but this is the extension that works only in python at the moment. Sean's background info on sprite animations is also below.

Scheme FSM run:

{{{> (define odd.A.even.B (make-FSM (list 'q0 'q1 'q2 'q3) (list 'a 'b) (list (list 'q1 'q2 ) (list 'q0 'q3 ) (list 'q3 'q0 ) (list 'q2 'q1 ) ) 'q0 (list 'q1)))

> (odd.A.even.B (list 'b 'b 'a 'b 'a 'b 'a ))

in state q0 with input b in state q2 with input b in state q0 with input a in state q1 with input b in state q3 with input a in state q2 with input b in state q0 with input a in state q1 FSM accepts (q1)

> (odd.A.even.B (list 'a 'b 'b 'a 'a 'b 'a ))

in state q0 with input a in state q1 with input b in state q3 with input b in state q1 with input a in state q0 with input a in state q1 with input b in state q3 with input a in state q2 FSM does not accept #f

> (odd.A.even.B (list 'a ))

in state q0 with input a in state q1 FSM accepts (q1)

> (odd.A.even.B (list ))

in state q0

FSM does not accept #f}}}

Excerpt from Sean's Sprite Animation handout:

What is sprite animation?

Sprites were originally invented as a method of quickly compositing several images together in two-dimensional video games. The term originally referred to a specific shortcut for rendering overlapping bitmaps onto a display device. As computer performance improved this optimization became unneccessary and the term evolved to refer specifically to the two dimensional images themselves that were integrated into a scene. (from Wikipedia - http://en.wikipedia.org/wiki/Sprite_%28computer_graphics%29) Sprite animation is what you commonly see in old 2D games for classic systems like the NES and SNES and in old computer games. In sprite animation, a sprite (or a character on the screen) is animated by sequentially displaying a series of pre-drawn images. This creates the illusion of movement.

What does sprite animation have to do with FSAs?

Usually, the image being displayed for a sprite onscreen during any specific frame of animation is a result of the image that came before and the keyboard input of the player.