Problem Description

Write a program, with all necessary classes, to simulate the behavior of a finite state automaton. It will first read the automaton definition from a file. Then, it will request a string from the console as input to the automaton. After reading the string, it will print accept or reject.

Finite State Automata

A finite-state machine M consists of

(a) A finite set I of input symbols

(d) A next state function f from S x I into S

(e) A set A of accepting states

(f) An initial state s in S

Example:

M = (I, O, S, f, g, s₀) where

I = { a, b }

S = { s₀,s₁}

A = { s₁ }

and f is defined by:

	f
I	a	b
S
s₀	s₀	s₁
s₁	s₁	s₁

This can be represented as a graph:

Input and Output

The input set I will always be the set of all possible characters (characters as represented internally in Java).

When it starts up, the program must prompt the user for:

1) The start state (a string)

2) The non-accepting states (one per line, each a string)

3) The accepting states (one per line, each a string)

Then, it must prompt the user for the next-state function. It does this state by state. That is, it asks the user

Enter the next-state function for state x

where x is each of the states in turn. For each state x, the user as many lines as necessary to define the next states after x, by entering on each line a single character, following by a space, followed by the string for the next state. An empty line signals the end of input for that state.

After the next-state function has been entered for all states, the program must write the next-state function to output, using a breadth-first search. When the program visits a state, it prints a line

Transitions from state x

where x is the name of the state and then, for each transition out of the state, it prints on subsequent lines the input character and the name of the next state.

Finally, the program must prompt the user for a string. If the string takes the finite state machine from the start state to an accepting state, the program prints accept. Otherwise, it prints reject. Note that if at any point the program is unable to find a next state corresponding to the current character in the string, the program should also print reject.

Data Structures

Define a FSA class using the adjacency list representation to represent the finite state automaton. You will also need State and Transition classes. Each state and transition must have an instance variable containing its label. The state label is the name of the state; the transition label is the character input that causes the transition.

The constructor should create an empty graph. You will need methods addTransition and addState to add states and transitions to the graph as your program reads the finite state automaton’s definition. Note that nothing will ever be removed from the graph.

You will need a bfSearch method to perform the breadth-first search of the graph. You should use this method to create a queue from which you will print the individual state transitions.

Finally, you will need a method run in the FSA class, which takes a string as input and returns true if the automaton ends in an accepting state and false otherwise. This method needs to determine which transition to follow for each character in the string, starting in the start state and using the first character to select an transition from the start state.