## 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).

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.