Programming Review Lab: Finite State Machines

Learning Objectives

1. Refresh programming skills including use of arrays and objects
2. Learn about finite state machines.

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

Assignment

1. Complete the program that simulates a finite state machine.
2. You are provided with the following. All files are found on the GitHub classroom. The invite for this assignment is: https://classroom.github.com/a/7DSlArMs
   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, new state, character) 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. Transitions. The shell for a list of transitions with methods and field variables you need to complete. See comments within the code for more instructions.
3. Be sure to modify the comments as appropriate and maintain good programming techniques

Submission instructions

1. Complete the SDR. Be aware that the form has changed! Include at least one more set of tests for your own machine along with any other tests you think are appropriate. Your testing report should probably not be more than a page and could be less.
2. Combine your SDR and all of your .java and testing files into one zip folder
3. 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