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.
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.
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.
This assignment is due at midnight on Monday, February 10, 1997.