Introduction to Objects: Finite State Machines

Learning Objectives

1. Refresh programming skills including use of arrays
2. Learn about objects
3. Learn about finite state machines.
4. Learn about unit testing

Overview of the program

A finite state machine is a simple machine that will either accept or reject an input. The Wikipedia article can give you an overview and so can many other resources on the Internet. To write a program for a finite state machine can be a complex task. However, to simulate one is MUCH easier. This program is to simulate a FSM

Prelab: Reading for details

1. Complete the reading for detail quiz at least 24 hours ahead of time.
2. If you pass with a 90% you are done.
3. If you score less than 90%, you must take a hard copy of this lab and highlight where the answers are to the quiz and bring it to lab. The quiz questions will be reposted about 24 hours before the lab so you can do this task.

Phase 1: Create a complete Software Design Report

1. Create your virtual machine
2. Install GitHub desktop
3. Get the provided code from the GitHub classroom
4. Install an UML diagramming tool on your machine. (Visio is a good one but there are other nice ones)
5. Design an UML class diagram for the provided code and the StateList class. You do not need to include the testing classes
6. Create a StateListUnitTest.java program similar to the existing unit test programs. Do NOT write the StateList class (you will lose points if you do). You may create the method headers so your unit test program can compile (similar to Transition.java that is provided) but no more!
7. Design at least one additional FSM and input to test your program. It should be a little more complex than the provide one.
8. Supplement your "lessons learned" with which UML diagramming tool you downloaded and why.

Phase 2: Complete the program

1. Complete the program that simulates a finite state machine.
   1. You are provided with the following.
      1. Transition.java. This class defines a single transition. Given a state and an input what is the next state.
      2. FSMDriver.java. This class contains a very simple driver. It instantiates a finite state machine from a file and then tests one string for acceptance.
      3. Simple. This is an example of a data file as follows
         1. Line 1: the alphabet of the machine (each one is a character)
         2. Line 2: the number of states in the machine (always integers)
         3. Line 3: which state is the initial state
         4. Next set of lines (until -1): one line (old state 'character' newstate) representing a transition.
         5. Last: a list of states (terminated with a -1) of final states
      4. FSM.java. The shell for the finite state machine with methods you need to complete. See comments within the code for more instructions
      5. TransitionList.java. The shell for a list of transitions with methods and field variables you need to complete. See comments within the code for more instructions.
      6. StateList.java. An empty shell for a list of final states. You must write this one yourself.
   2. Be sure to modify the comments as appropriate and maintain good programming techniques
2. Write a Software Development report.
3. Combine your SDR and all of your .java and testing files into one zip folder
4. Submit the zip folder on Canvas by the due data specific there.

Restriction:

It is very likely that there are programs that can be downloaded that can simulate a FSM. You are not allowed to even look at these. The code provided is what you should use. This assignment is to bring back your programming skills.

Challenges

1. Don't use some/all of the provided code. If this is the case, indicate in an obvious way that you did this in your SDR and your documentation of the code.
2. For extra credit, convert it to a nondeterministic finite state machine

Post lab

1. Compare and contrast your solution to the posted solution.
2. In your writeup, indicate anything that was different between the two and comment on that. (There will always be some differences. Your code might be better.)
3. Also include at least two things that you learned from the comparison.