[Home]

Why use finite automata?

This is the third page of our tutorial, and it may seem somewhat late now to ask this question. Indeed, this is the question that a student may (and should) justly demand an answer to even before starting to read the tutorial! But the only reason that we have strained the reader's patience so far is: had we listed the possible uses of finite automata earlier, it would most possibly have made him/her think that finite automata are very difficult things to understand. Indeed, there does not seem to be another belief that is so wrong, yet so popular, as that "brilliant concepts are difficult concepts". Well, we for one do not believe in this motto, and hope to find the reader on our side once he/she completes reading the tutorial.

An internal state machine is a machine with a memory. We go on a bit further and say, that any machine with a memory is an internal state machine. The finiteness condition in the definition of finite automata is the natural restriction imposed by the fact that computers cannot handle infinite sets. (However, there are some important variants of finite automata that sort of allow infinite sets. We shall learn about some such variants in a later page.) Viewed in this light, the above question reduces to "Why use machines with memories?"

To the modern reader the answer should be more than obvious. What is a computer but a machine with a memory? Almost every application that runs on a computer is some form of finite automata or other. Here is a list that makes no pretence of being comprehensive:

The compilers that compile your codes in C, ForTran, Java or Lisp or whatever language we may be using --- are all made up of (variants of) finite automata. The thick books about compiler designs essentially tell you how to build the various finite automata components in a compiler.
Do you use LaTeX to typeset your documents? How does it work ? How does it remember to indent things properly inside a block that you have started ten lines back? Only because the LaTeX compiler has a memory!
The very HTML file that you are reading requires finite automata for parsing it.
Ever thought of writing a program to make a calculator that accepts mathematical formulas like 34.7*67^(4+9) , and computes the value keeping track of precedences? If not, try your hand at it! And you will see how confusing it is to write it without finite automata, and how easy with it!
Any editor that you use has lots of finite automata running behind the screen.
Ever played games like Quake or Diablo, the so-called 3D role playing games where you control some character to fight against a host of monsters and robots? All those robots and monsters are made up of finite automata, much like the simple robot that we saw in the first page of this tutorial.
Finite automata are indispesible in hardware also! The mother board of your computer is implementing a huge finite automaton. Also, most of the "intelligent" electronic gadget that you see around you (eg, automatic traffic signals, radio controlled toys, automatic elevator controls) use finite automata at various levels.

Well, if we go on like this the list will extend up to infinity. So we shall pause here, and show one very important class of application namely language recognition. This application will show how finite automata are used in editors and in the first phase of compilers.

A concrete application : Lexical analysis

Consider a huge C-code with lots of embedded comments. As the reader should know already, C-comments are delimited by a starting /* and a trailing */, and comments cannot be nested. When a compiler reads the code it strips all the comments off the code. How is this stripping done? To understand this we shall write a that portion of the compiler which strips comments. Our compiler will read the program file character by character. Since the program may be very huge, it makes no attempt to store huge chunks of the code at a time. Keeping this restriction in mind we know that our compiler (which will presently emerge as a finite automaton) has input set consisting of all the possible characters that may be present in C code. Now let us delve into the mind of the compiler.

When it starts reading the file it is outside any comment. It goes on reading character after character from the file (and tossing the characters in the output file) until it meets the first /. Then it knows that t has encountered a possible start of comment. To make sure it reads the next character. If it is a * then the compiler is certain that it is inside a comment. In this case the compiler keeps on reading the file, but now throws away the characters in the garbage bin. If it was not a * then of course the compiler understands that it is outside any comment and keeps on copying the characters read into the output file. In our imaginary voyage through the mind of the compiler, let us again imagine ourselves in the situation where the compiler is inside a comment. If it happens to meet a * it knows that it may be a possible end of comment. So after trashing the * it reads the next character. If it is a / then the comment has indeed ended and the compiler is again in a region that is outside any comment.

Let us take one more look at the above confusing description paying particular attention to the bold phrases. There are four of them:

outside any comment
possible start of comment
inside a comment
possible end of comment

The behaviour of the compiler depends which of the four states ie is currently in. Well, there is no hiding after we have already used the word "state". Yes, these are the 4 states of the finite automaton. What are the inputs? We have already said that the input set consists of all possible characters that may be found in a C-file. But that's a pretty large set. One further look at the lat paragraph will, however, convince the reader that all that the automaton really has to know is whether the character is a * or / or something else. But is that all? Not quite! Our automaton needs some way to know when the end of file has been reached. You surely cannot leave the machine to imitate poor Oliver, "always asking for more"! So we need another special input symbol which we shall call EOF (End Of File). Thus we shall have four inputs:

*
/
EOF
<anything else>

How many outputs shall we have? Well, we shall need 7 of them:

PC : Print the Currently read character in the output file
T : Trash the currently read character
S: Store the currently read character in a temporary storage.
D : issue the message "Done".
E : issue the message "Error".
PSC : Print the Stored character followed by the Current character.
PSD : Print the Stored character and say "Done".

Without further ado we give the two tables corresponding to the output controlling and the state controlling functions:

Inputs

States

	`*`	`/`	EOF	<anything else>
outside any comment	PC	S	D	PC
possible start of comment	T	PSC	PSD	PSC
inside comment	S	T	E	T
possible end of comment	T	T	D	T

The state controlling function is equally obvious.

Inputs

States

	`*`	`/`	EOF	<anything else>
outside any comment	outside	start	outside	outside
possible start of comment	inside	outside	outside	outside
inside comment	end	inside	inside	inside
possible end of comment	inside	outside	inside	inside

Here, in the second table, "start" is an abbreviation for "possible start of comment", "inside" is an abbreviation for "inside comment", and so on. The reader is requested to try his/her hand at implementing the above finite automaton in some standard computer language like C or ForTran.

In the next page we shall continue with a more sophisticated version of the same example.

Table of contents

Why use finite automata?

A concrete application : Lexical analysis