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