Glossary Table of 
Contents
Index 
(Note: this being the green circle route, or easiest way, through the material, we will include a very intuitive development of the concept of a finite state automaton. There will be numerous animations and illustrations sprinkled throughout with links to even more if the reader feels a need for more. We are just now in the process of reworking our animation modules so that they can be invoked more "seamlessly" in a hypertextbook like this. Below is a short example of this concept.)
Well, here we are. Already staring one of these inscrutable mathematical phrases in the face. What is a finite state automaton, and how could anyone come up with a name like that to describe anything? Good question, and we'll start by looking for the answer. In order to understand this phrase, there are three terms that need exploration:
 | automaton |
| state |
| finite state |
An automaton is simply a device that functions automatically. A coke machine is
an automaton---it takes money as input and dispenses a can of pop as output, all
automatically. A drive-through car wash is an automaton. So is an automatic
teller machine. For this lesson, though, the word "automaton" is
synonymous with "computer." So, we could refer to a finite state automaton
as a finite state computer instead. In some of the literature the term used is
finite state machine rather than finite state automaton. In all cases the
term just refers to a restricted form of a computer. ...more (Note:
These "...more" links are not yet implemented. The idea should be clear.
Wherever a "...more" link is found, the reader can follow that link to
read more about the topic under discussion, allowing readers to continue studying a
concept that may not be clear.)
The word state refers to a state of being. One can ask of a finite state automaton
at any point in its calculation what state it is in. A coke machine could be in the
state of having processed thirty-five cents as input. At this point it would be
waiting for more money to be input (if not, let us know where that machine is!). A
car wash could be in the state of having finished the main wash and about to start the
rinse. An ATM could be in the state of just starting, waiting for a new customer to
insert an ATM card. The current state of an automaton is really a form of memory
that reveals what stage of the calculation the automaton is in so that it knows how to
proceed in completing the calculation. ...more
A finite state automaton is an automaton (or computer) that has only a finite, fixed
number of states that it can be in during any point of a calculation. A coke machine
only has a finite number of states representing how much money has been inserted so far
(if more than the maximum amount possible is input, the change is simply returned).
A car wash has a state for each phase of the wash. It is reasonable to require that
any model of a computer we analyze for solving real problems be restricted to having only
a finite number of states. After all, in real life nothing is infinite, so we could
never expect to build a computer with an infinite number of anything, states
included. ...more
In summary, a finite state automaton is a very simple computer. Just remember these points:
| In our study of computability, the finite state automaton is the simplest form of computer we will study. |
| There are many problems that we cannot solve with a finite state automaton that we can solve with more powerful models of a computer. |
| In spite of its limitation, the finite state automaton is quite useful in practice. We'll see some examples later. |
(Note: this track would proceed much further, eventually arriving at the mathematical definition of a finite state automaton by way of lots of intuition. Illustrations and animations would be sprinkled throughout. See the black diamond version of the definition for examples of incorporating animations.)
Glossary Table of Contents
Index