Finite State Automata

black.gif (937 bytes)

line_with_eyes.gif (232 bytes)

 arrow_left.gif (1076 bytes) Glossary     Table of arrow_uo.gif (1110 bytes) Contents      Index arrow_right.gif (1078 bytes)

Up

(Note:  the black diamond route is the most challenging approach to learning about the material, with the exception that multiple black diamonds represent even more challenging routes.  Usually what this means is that a rather terse, abstract, and mathematical approach to the material is given with only a few examples and illustrations.  An example is given below, albeit one that is not completely fleshed out).

A finite state automaton, or finite state machine, is a restricted mathematical model of a computer (i.e., a restricted type of algorithm).  A finite state automaton has five components:

  1. a set of states

  2. a finite input alphabet from which input strings can be constructed

  3. a transition function that describes how the automaton changes states as it processes an input string

  4. a single designated starting state

  5. a set of accepting states

Formally,  a finite state automaton can be defined as follows:

(Note:  The following definition uses special symbols from the Microsoft Symbol font.  The symbols may be unreadable unless your browser is running on PC with a Microsoft operating system.  Mathematical notation is one of the challenges yet to be met in the construction of Snapshots.   Mathematics could be inserted by way of .gif images (e.g., via the latex2html utility).  This is an unsatisfactory solution, however.  The best solution is to use MathML.  Right now software for including and displaying MathML is in short supply.  All reports indicate, however, that all of the popular browsers will eventually be able to render MathML directly.  For the time being, we plan to proceed by using a commercial MathML editor.)

Definition

A finite state automaton (fsa) is a five-tuple, M = (Q, S, d, q0, F), where Q is a finite set of states, S is a finite input alphabet, d is a transition function, d: Q ´ S ® Q, q0 Î Q is the starting state, and F--a subset of Q--is a set of accepting states.

An fsa functions as follows.   It always begins operation in the starting state.  When provided a string of symbols over the input alphabet, it processes the string one symbol at a time from left to right.  As the input string is processed, the fsa changes states based on the current state and the current input symbol being processed.  For instance, if the fsa is in state q and the symbol being processed is a, then the next state of the fsa is determined by the value of the transition function at q and a:  d(q,a) = r.  After processing the entire string, the fsa is found in some state s.   If s is a member of the accepting states, then the input string w is said to be accepted by the fsa, otherwise the string is considered rejected.

Example 1.

A finite state automaton is typically depicted as a directed graph.  The start state is denoted by a single arrow entering the start state that has no origin.  In this example, which is a finite state automaton that determines whether a binary string has odd parity, the only non accepting state is colored red.  The single accepting state is colored green.

even-parity.gif (775 bytes)

(Note:  we are close to being able to insert images directly from the finite state automaton animator---see the example applet at the end of this page.  This will make all static finite state automaton examples and all animation examples look the same, giving more consistency to the text.)

Example 2

The animated example given at the end of this description demonstrates a finite state automaton that recognizes strings of symbols that are valid numbers in the Ada programming language.   You can see that the fsa is really a directed, labeled graph.  For this example fsa, there are ten states in Q each depicted as a node in the graph, S is the set of all ASCII symbols (that is, the input alphabet for this fsa is all of the symbols that can be entered from a standard keyboard; strings that can be submitted to this fsa for processing are built from these symbols), the transition function d is defined by the transition arrows connecting the states in the graph, the start state is the circle with the > symbol attached to its left, and the accept states are those with a double circle.

A transition is shown in the graph as an arrow labeled with an input symbol that originates in node q and ends in node r.  (If there is no arrow with the label in question, the fsa simply halts and rejects its input.) 

Some of the arrows in this example are labeled with a range of characters, for example, 0-9.  This just means that any of the characters in the specified range causes the fsa to follow this transition.

</COMMENT>

Now to see an example of how to implement a finite state automaton as a program, click on the button below. 

Apparently your browser doesn't do Java.  

click the button to view the fsa program example

Finally, to see how the language accepted by this finite state automaton can be generated by a regular language, click on the image below.  (Note:  this grammar animation does not match the finite state automaton at the moment.  We now have a way to bring up animations starting with selected examples rather than requiring the user to select the proper animation from the applet.  We are in the process of implementing this.)

binoc.gif (2206 bytes)

click on the image to view the grammar animation

 

(Note:  The above links are not an example of how we intend to actually include animations in the text.  For one thing, the animations are a bit disjointed right now.  There would be more development of the ideas, for example, before the grammar animator would be invoked at this point.   Also, at present, we insert examples by way of links to the animation applets.   The intent is to provide far more animations throughout the text, with most examples displayed directly in the text. No link to a separate page would be needed in these cases, making the presentation more "seamless."  For exercises, it may still be best to have links to separate applets that include more options, such as the capability to save, print, and electronically submit fsa's, programs, or grammars that a student constructs with the applet.  We are just a step away from this right now.)

 arrow_left.gif (1076 bytes) Glossary     Table of arrow_uo.gif (1110 bytes) Contents      Index arrow_right.gif (1078 bytes)

Up