Programming Project 1

CSCI 371                                                    Due Fri. Feb. 3

Simulate a FSM

Purpose: Hardcode a specific DFSM to accept or reject input strings.

Method: The easiest way to program a specific DFSM is to use a 2-D array to model the transition function.  The row index would be the current state, the column index would correspond to an input character and the value in the array is the next state.  Let's look at the example on page 58.  The array representing this DFSM could look like:

You would start with the current state as the start state (in this case, state 0), read in a character, use the current state and the input character to index into the array to get the next state.  Then you repeat until you get to the end of the string.  If, at this point, the current state is an accept state (in this case, only state 0) then you accept, otherwise reject the string.

This DFSM example used a dead state.  We talked about removing the need to have a dead state by allowing a state to not have a character coming out of it, such that if we are in that state and we get a character that has no transition then we can reject the string at that point.  We could incorporate this idea into our program by having the next-state entry be, for example, -1 for the entries that have no transition for that current-state/input pair.  Then if we are ever in the -1 current state we can reject the string at that point.

Our problem: Use the DFSM shown in Exercise 1 on page 121.  The input will be several strings, one per line.  For each input string, print the string and the word "Accept" or "Reject".