CS 2073 Section 2, Fall 1997
Assignment 3: if/else/switch: Finite State Automata

For this assignment, you will write a C program called fsa.c that performs actions of a Finite State Automaton, or FSA. An FSA 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 FSA

An FSA consists of several states and rules, and the alphabet of characters the strings will come from. The states are the locations in the FSA; the FSA is in one state at any given time. The initial state is the state the FSA starts out in; when the FSA gets a character, it may go into a different state depending on what the character is. If the FSA ends up in the final state and there are no more characters to get, the FSA accepts the string, otherwise it rejects it. We can draw FSA'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. FSA's are used a lot in computer science and electrical engineering, in designing clocked logic and state machines in programs; if you'd like to know more about FSA's, see the instructor's ramblings on the topic.

A Sample 3-State FSA

Consider the following three-state FSA over the alphabet {a, b} (lynx users go here for an ASCII picture of the FSA).

FSA Picture

In this FSA, 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 FSA. 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 FSA. 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 FSA 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 FSA 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 FSA 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 FSA and write a C program that implements it. Each student will implement a different FSA. To get a description of your FSA, run the program called genfsa in the instructor's bin directory on runner with your login name as the parameter (i.e., type ~djimenez/bin/genfsa followed by your login name). Some FSAs will be over the alphabet {a, b} and have five states; others will be over the alphabet {a, b, c} and have three states. Running the genfsa 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.

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 instructor 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 instructor will see when your program is checked, type ~djimenez/bin/checkfsa followed by your login name after compiling your fsa.c into a binary called fsa. 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 FSA. Click here for some sample output from the genfsa and checkfsa programs.

Turning in the Assignment

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

Mail -s "CS2073 Assignment 3" djimenez@ringer.cs.utsa.edu < fsa.c

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

As always, describe your experiences with this program in your progress report.

This assignment is due at midnight on Wednesday, September 24, 1997.