CS 2073 Section 2, Spring 2009
Assignment 3: if/else/switch: Finite State Machine

For this assignment, you will write a C program called fsm.c that performs actions of a Finite State Machine, or FSM. An FSM is a simple computational device that examines a sequence of characters (a string) one character at a time, and at the end deciding whether to "accept" or "reject" the string.

Definition of an FSM

An FSM consists of several states and rules, and the alphabet of characters the strings will come from. The states are the locations in the FSM; the FSM is in one state at any given time. The initial state is the state the FSM starts out in; when the FSM gets a character, it may go into a different state depending on what the character is. If the FSM ends up in the final state and there are no more characters to get, the FSM accepts the string, otherwise it rejects it. We can draw FSM's with states as circles and the rules to get from one state to the other as labeled arrows connecting the circles. The labels tell us where to go next given a certain character as input. FSM's are used a lot in electrical engineering, in designing clocked logic and state machines in programs.

A Sample 3-State FSM

Consider the following three-state FSM over the alphabet {a, b}:

FSM Picture

In this FSM, state 1 is the initial state (indicated by the wedge at the top) and state 3 is the final state (indicated by the double-circle). Suppose we present the string bbaa to the FSM. The first character, b, takes us from the initial state (1) to state 2. The second character, another b, takes us from state 2 back to state 2 again. The third character, this time an a, takes us from state 2 to state 1. From state 1, the final a takes us to the final state, state 3. Since there are no more characters and we are in the final state, the string bbaa is accepted.

When we are not in the final state at the end of the string, the string is not accepted. Note that we may pass through the final state, as in the case of the string aab, but the string is not accepted because we end up at state 2 at the end of the string.

We can write a C program to simulate the behavior of an FSM. We'll the C function getchar() to get the next character, and have the user type a dollar sign ($) to signal the end of input ($ is not in our alphabet; it's just a symbol that means "no more characters"). The C program will keep an integer variable called state, initialized to the initial state, and use a while loop to get characters until it gets a dollar sign. If the current state is the final state, the C program will print "accepted."; otherwise it will print "not accepted." Here is a C program for the FSM pictured above. When compiled and run, it sits waiting for a string to be entered. When the user types, for example, abababa$ and then ENTER, the program will begin pushing the string through the FSM one character at a time until the dollar sign is encountered. At the end, it will print "not accepted." because abababa does not leave the FSM in its final state. Try compiling the program yourself, and see what it does on different inputs.

For this Assignment

Your assignment is to take a description of an FSM and write a C program that implements it. Each student will implement a different FSM. To get a description of your FSM, run the program called genfsm in the professor's bin directory on the main system with your login name as the parameter (i.e., type ~dj/bin/genfsm followed by your login name). Your FSM will be over the alphabet {a, b} and have five states. Running the genfsm program will give you the initial and final states, a complete description of where to go from which state on which input, and some examples of accepted ("yes" examples) and not accepted ("no" examples) strings. The initial state is state #0, and the final state is the last state given by the program i.e. state #4.

Your program should behave similarly to the sample C program; it should not prompt for input and should print "accepted." or "not accepted." in lowercase depending on whether the string is accepted. Your program should print nothing else. Note the periods at the end of "accepted." and "not accepted." The teaching assistant will check your program automatically using another program that feeds strings into your program and examines the output, so your program must conform exactly to these specifications. To see what the teaching assistant will see when your program is checked, type ~dj/bin/checkfsm followed by your login name after compiling your fsm.c into a binary called fsm. You must run checkfsm in the directory where your fsm program is located. If the program seems to hang, you probably have a bug in your program causing it not to terminate; make sure you use getchar() each time through the while loop. Your program should work correctly on all the sample inputs, and any other inputs to the FSM. Click here for some sample output from the genfsm and checkfsm programs.

Turning in the Assignment

To turn in this assignment, e-mail your well-commented source code to the teaching assistant with the command:

mail -s "CS2073 Assignment 3" ytian@cs.utsa.edu < fsm.c

The program will be graded using the checkfsm program, so make sure it works with that.

This assignment is due at midnight on Tuesday, February 24, 2009.