Finite Automata
Introduction to Finite Automata
In this chapter we are going to study a class of machines called finite automata.
Finite automata are computing devices that accept/recognize regular languages and are used
to model operations of many systems we find in practice. Their operations can be simulated
by a very simple computer program. A kind of systems finite automnata can model and
a computer program to simulate their operations are discussed
later.
Let us consider the operation of a soft drink vending machine which charges 15 cents for a can.
Pretend that you are the machine. Initially you are waiting for a customer to come and put some coins,
that is, you are
in the waiting-for-customer state.
Let us assume that only nickels and dimes are used for simplicity.
When a customer comes and
puts in the first coin, say a dime, you are no longer in the waiting-for-customer state.
You have received 10 cents
and are waiting for more coins to come. So we might say you are in the 10-cents state.
If the customer puts in a nickel, then you have now received 15 cents and you wait for the customer
to select a soft drink. So you are in another state, say 15-cents state. When the customer selects
a soft drink, you must give the customer
a can of soft drink. After that you stay in that state until another coin is put in to start the process
anew or you may terminate the operation and start all over from the initial state. The states and the transitions between them of this vending machine can be
represented with the diagram below.
In the figure, circles represent states and arrows state transitions.
Ds on arrows represent a dime and Ns a nickel.
It is assumed that the machine terminates its operation when it receives 15 cents or more.
Click "NICKEL" or "DIME" in the figure and see how it operates (see how arrows turn red).
In this example you as a vending machine have gone through (transitions between) a number of
states responding to the inputs
from the customer (coins in this case). A vending machine looked at this way is
an example of
finite automaton.
We have learned that regular languages are represented by regular expressions
and conversely. In the next few chapters first we are going to learn different kinds of
finite automata, and equivalence and conversions between them. Then we are going to see
that for every
regular language a unique finite automaton can be constructed which can recognize
the language
(i.e. tell whether or not
a given string belongs to the regular language).
We are then going to study how finite automata can be used to simulate operations of
systems we see in practice.
Unfortunately not all languages and systems are simple like regular languages or
finite automata. There are languages which are not regular and which, therefore, can not be
recognized by finite automata. We are going to learn languages which are not regular
and ways to test languages for non-regularity.
Later we are going to learn an extension of finite automata
called Turing machines.
Though Turing machines are simple modification of finite automata, they are
much more powerful computing devices than finite automata. In fact Turing machines
are as powerful as computers and it is
generally believed, though not proven, that any computation human beings do (with or without computers)
can be performed by Turing machines.
In this chapter we are going to study definitions and properties of
deterministic finite automata which are
one of several types of finite automata.
Next -- Definition of Deterministic Finite Automaton
Back to Study Schedule
Back to Table of Contents