##### 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).