Finite Automata – I

Formally, “Finite automation is mathematical model of a system with discrete inputs and outputs”. Finite automata describe a system or computer that goes through a fix number of states and has fixed inputs.

For people new to the topic, it is easier to understand using an example.

In this simple example, P and Q are states and ‘a’ is called input alphabet. From the figure we can see that there is transition from one state to another state on receiving the input ‘a’.

Basic Definitions

• A Finite automation (FA) consists of a finite set of states and a set of transitions from state to state that occur on a input symbols chosen from an alphabet ∑.
• For each input symbol there is exactly one transition out to another state.
• q0 is the initial state. There is a state from which automation start all the transitions.
• Some states are accepting states or Final states.

Example of Finite Automata

 Consider an finite automata that accepts even numbers binary equivalent.
meaning , 10 in binary is 1010.

At q0 both 0 and 1 are even because they are 0, so q0 is accepting state. Now the automata must read the 1010 which is equal to Ten.

Step 1: 
At First it received 1 and transition to q1

Step 2:
Then we received 0 and transition to q3

Step 3:
Then we received a 1 and transition to q2.

Step 4:
Finally, we received a 0, and goes to q0 with is an accepting state.


Now, consider another example, automata reads 1100 which is decimal 12.

Step 1:
First automata reads a 1, and automata goes to q1.

Step 2:
At q1, automata gets another 1 and goes back to q0 which is accepting state.

Step 3:
At q0, receives a 0 and goes to q2 state.

Step 4:
Finally, automata receives a 0 and goes to q0 final state.

Transition Function 

A transition function is defined as δ (q, a).
Here q is some state and reads symbol ‘a’, then enters δ (q, a) and moves to next state in automata.

If the next state is an accepting state entire string is accepted successfully.