- Finite automata
- State transition diagram
- State transition table

Let us now formally define 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 q

Then a

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

- 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".

- Note that is a function. Thus for
**each state**q of Q and for**each symbol**a of , (q, a) must be specified.

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

- 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

Transition functions can also be represented by tables as seen below. They are called

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.

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.

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.

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 can also be thought of as the device shown below consisting of a tape and a control circuit which satisfy the following conditions:

- The tape has the left end and extends to the right without an end.

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

- The tape has a read only head.
- The head is always at the leftmost square at the beginning of the operation.

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

- There is a finite control which determines the state of the automaton and also controls the movement of the head.

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.

Click Yes or No , then Submit.

There are two sets of questions.