[Home]

Table of contents

Finite automaton tutorial

Introduction

This is a tutorial on Finite Automata. "Why on Finite Automata out of all things?" , one might reasonably ask. The reason is that they are useful, easy to understand (at least the basic ideas), they pave the way for a lot of other ideas, and there does not seem to be good internet tutorials on the subject. Long introductions hardly ever make good tutorials. So let us conclude the introduction right here, and move over to something more interesting.

What is an Automaton?

The word "automata" is the plural of the word "automaton" which simply means any machine. We all know what a machine is. Nevertheless, we shall review the concept here. To do so we shall adopt the "users' point of view", i.e., we shall not bother ourselves with how the machine works internally in terms of springs and gears, but rather what it does.

The most simple definition of a machine seems to be that
it is a black-box into which some input is fed, and as a result some output comes out. The relationship between the input and the output (i.e., which output results from which input) depends on the particular machine at hand.
Thus a machine seems to comprise three things :
  1. A set of inputs ($A$)
  2. A set of outputs ($B$)
  3. Some rule that tells the machine which output to produce on which input (a function $f : A -> B$)

Here is one example. Suppose I am trying to build a Humptydumpty that imitates human nature to a crude extent. He sees if you are smiling at him or punching him. Depending on that he can do two things : he can smile back at you or he can scowl. Here Humptydumpty is a machine with
input set ($A$) = {smile, punch},
and
output set ($B$) = {smile back,scowl}
We want the following input-output relation ($f$) :
If you smile at it, Humpty smiles back to you i.e., $f$(smile)=smile back
and
Humpty scowls at you if you punch it, i.e., $f$(punch)=scowl

Humptydumpty version 1

InputsOutputs
Smile back

Scowl

Now try out the following sequence of input (i.e. sequence of button preses in that order, and note the sequence of outputs :
smile, punch, punch punch , punch, punch, smile, smile.
Thus, you start with a smile, and then follow it up with four harsh punches, and finally you smile at Humpty twice. The output sequence is of course
smile back, scowl, scowl, scowl,scowl,scowl, smile back, smile back.
That is quite as expected from our robotic Humpty! But is this expected from a human being even if his responses are confined to just smiling back and scowling ? Surly not! If you punch a fellow four times, even the sweetest smile after that is unlikely to elicit a smile from him. He will hardly forget the thrashing you have given him so recently. But our benign Humpty does not seem to bear any grudge against you even after any number of punching. The reason is simple : he has no memory at all to remember all those punches! Now memory is one of the essential things that control human action, and to imitate human action more closely we need a Humptydumpty with a memory. That is what we plan to build in the next example. But before going into that let us take another look at our simple Humpty.

Our Humpty is characterized by three things ($A,B,f$). Out of these $A$ and $B$ are finite sets, and $f$ is a function from $A$ to $B$. We shall assume that $B$ has no unnecessary element, i.e., every member in $B$ is a possible output (for some appropriate input). In mathematical terms we mean to say that $f$ is onto $B$. Then it is easy to see that that $B$ cannot have more elements in it than $A$ has. Thus,
Observation: There cannot be more outputs than inputs.
In plain English, it says that if you have to get a lot you have to do a lot. Not the most promising prospect!

Now take a look at another version of Humptydumpty --- a more sophisticated one.

Humptydumpty version 2

Inputs Outputs
Normal

Smile

Raise eyebrow

Scowl

Growl

Grimace


Well, this Humpty looks similar to the last version. It has the same input set as the last one, but the output set is much larger. So he accommodates a more varied range of human activities. But is that all the difference ? Observe that the size of the output set is 6 which is larger than the size of the input set. Thus either some of the outputs never occur or the new Humpty is not the old simple Humpty any more for which the last observation holds.

Play around with the input buttons for ome time to convince yourself that all the outputs occur at some time or other. Do you notice something else, too? Carry out the following experiment:

EXPERIMENT : First press the RESET button to cancel the effects of any input that you have possibly typed earlier. Then give the following input sequence
smile punch, punch, punch, smile, smile.
Lo, and behold! This new Humpty does not react to all the punches in the same way. The first smile did cause it to smile back, but the second smile (after the punches) failed to do so. Not only that, after the first punch Humpty looked surprised, the second punch caused him to scowl, the third punch made him growl. We shall not discuss here whether this is a justifiable action on part of Humpty, but we want to emphasize that now he has a memory. He can now distinguish the first punch from the second one. More generally, his reaction to some input is partly guided by the past sequence of inputs.

How did we endow him with a memory? Simple! Behind the screen we have a little box called the "mind" that you cannot see. In this box we keep Humpty's current "mental state". Our Humpty has a simple mind that can have only 5 mental states :
ordinary, happy, angry, furious, surprised
Each time you either punch or smile at him, Humpty behaves differently depending on his current "mental state". When he is in his "ordinary" mental state, a punch causes him to raise his eyebrows. But if he is angry (i.e., the mental state currently in the box mind is "angry") then he growls. Of course, as in case of a human being, the mental state itself changes depending on the last mental state and the current input.

Too confusing? It might help you to take a look at the inside of the Humpty's mind-box. Our benign, oval friend will not mind if you peep into his mind. All that you have to do is to press RESET, and then press the Mind Toggler button once. Now carry out whatever experiment you want, the mental states will be displayed after each step.

Now let us jot down our findings in general terms. Unlike our first Humpty, the new one has three sets and two functions. The sets are
input set ($A$), output set ($B$) and set of mental states ($S$).
Henceforth we shall call a mental state by its more usual name internal state or simply state. The two functions involved are the one controlling the output, and the one controlling the mind (i.e., internal states):
$f:A\times S\rightarrow A$ and $g:A\times S\rightarrow S.$
If you are at (internal) state $s$ now and you receive the input $a$ then you produce output $f(a,s$), and internally move to state $g(a,s$).

Definition: Such a machine is called an internal state machine. If the set $S$ of internal sets is finite then we call the machine a finite state machine or (more impressively) a finite automaton.

In the next page we shall see some uses and implementation of this concept.