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

Phase 1: Create a complete Software Design Report

1. Create your virtual machine
   • You can reuse your machine from last semester or create a new one (using the same instructions).
2. Install GitHub desktop
3. Get the provided code from the GitHub classroom
   • link: https://classroom.github.com/a/5ZPr_s45
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