Finite Automata

Definition of Deterministic Finite Automata



Subjects to be Learned

Contents

Here we are going to formally define finite automata, in particular deterministic finite automata and see some examples. Finite automata recognize regular languages and, conversely, any language that is recognized by a finite automaton is regular. There are other types of finite automata such as nondeterministic finite automata and nondeterministic automata with and they are going to be studied later.

Let us now formally define deterministic finite automaton.

Definition of deterministic finite automaton

Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to Q ,   let q0 be a state in Q and let A be a subset of Q. We call the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states.
Then a deterministic finite automaton is a 5-tuple < Q , , q0 , , A >

Notes on the definition
  1. The set Q in the above definition is simply a set with a finite number of elements. Its elements can, however, be interpreted as a state that the system (automaton) is in. Thus in the example of vending machine, for example, the states of the machine such as "waiting for a customer to put a coin in", "have received 5 cents" etc. are the elements of Q. "Waiting for a customer to put a coin in" can be considered the initial state of this automaton and the state in which the machine gives out a soda can can be considered the accepting state.
  2. The transition function is also called a next state function meaning that the automaton moves into the state (q, a) if it receives the input symbol a while in state q.
    Thus in the example of vending machine, if q is the initial state and a nickel is put in, then (q, a) is equal to "have received 5 cents".
  3. Note that is a function. Thus for each state q of Q and for each symbol a of ,   (q, a) must be specified.
  4. The accepting states are used to distinguish sequences of inputs given to the finite automaton. If the finite automaton is in an accepting state when the input ceases to come, the sequence of input symbols given to the finite automaton is "accepted". Otherwise it is not accepted. For example, in the Example 1 below, the string a is accepted by the finite automaton. But any other strings such as aa, aaa, etc. are not accepted.
  5. A deterministic finite automaton is also called simply a "finite automaton". Abbreviations such as FA and DFA are used to denote deterministic finite automaton.


DFAs are often represented by digraphs called (state) transition diagram. The vertices (denoted by single circles) of a transition diagram represent the states of the DFA and the arcs labeled with an input symbol correspond to the transitions. An arc ( p , q ) from vertex p to vertex q with label represents the transition (p, ) = q . The accepting states are indicated by double circles.
Transition functions can also be represented by tables as seen below. They are called transition table.

Examples of finite automaton

Example 1: Q = { 0, 1, 2 }, = { a }, A = { 1 }, the initial state is 0 and is as shown in the following table.

           
State (q) Input (a) Next State ( (q, a) )
0 a 1
1 a 2
2 a 2








A state transition diagram for this DFA is given below.



           



If the alphabet of the Example 1 is changed to { a, b } in stead of { a }, then we need a DFA such as shown in the following examle to accept the same string a. It is a little more complex DFA.

Example 2: Q = { 0, 1, 2 }, = { a, b }, A = { 1 }, the initial state is 0 and is as shown in the following table.

           
State (q) Input (a) Next State ( (q, a) )
0 a 1
0 b 2
1 a 2
1 b 2
2 a 2
2 b 2












Note that for each state there are two rows in the table for corresponding to the symbols a and b, while in the Example 1 there is only one row for each state.

A state transition diagram for this DFA is given below.



           


A DFA that accepts all strings consisting of only symbol a over the alphabet { a, b } is the next example.

Example 3: Q = { 0, 1 }, = { a, b }, A = { 0 }, the initial state is 0 and is as shown in the following table.

           
State (q) Input (a) Next State ( (q, a) )
0 a 0
0 b 1
1 a 1
1 b 1










A state transition diagram for this DFA is given below.



           



Example 4: For the example of vending machine of the previous section, Q = { 0, 5, 10, 15, 20 }, = { D, N }, A = { 15, 20 }, the initial state q0 = 0. If we make it a DFA, its transition function is as shown in the following table.

           
State (q) Input (a) Next State ( (q, a) )
0 N 5
0 D 10
5 N 10
5 D 15
10 N 15
10 D 20
15 N 5
15 D 10
20 N 5
20 D 10





















           





A finite automaton as a machine

A finite automaton can also be thought of as the device shown below consisting of a tape and a control circuit which satisfy the following conditions:
  1. The tape has the left end and extends to the right without an end.
  2. The tape is divide into squares in each of which a symbol can be written prior to the start of the operation of the automaton.
  3. The tape has a read only head.
  4. The head is always at the leftmost square at the beginning of the operation.
  5. The head moves to the right one square every time it reads a symbol.
    It never moves to the left. When it sees no symbol, it stops and the automaton terminates its operation.
  6. There is a finite control which determines the state of the automaton and also controls the movement of the head.


           






Operation of finite automata

Let us see how an automaton operates when it is given some inputs. As an example let us consider the DFA of Example 3 above.
Initially it is in state 0. When zero or more a's are given as an input to it, it stays in state 0 while it reads all the a's (without breaks) on the tape. Since the state 0 is also the accepting state, when all the a's on the tape are read, the DFA is in the accepting state. Thus this automaton accepts any string of a's. If b is read while it is in state 0 (initially or after reading some a's), it moves to state 1. Once it gets to state 1, then no matter what symbol is read, this DFA never leaves state 1. Hence when b appears anywhere in the input, it goes into state 1 and the input string is not accepted by the DFA. For example strings aaa, aaaaaa etc. are accepted but strings such as aaba, b etc. are not accepted by this automaton.



Test Your Understanding of Definition of DFA

Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
There are two sets of questions.












Next --- * and its Properties

Back to Study Schedule

Back to Table of Contents