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

 States and Symbol

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.

 FA is denoted by 5-tuple ( Q, ∑, δ, q0, F ⊂) Q -> Finite number of States ( q0,q1,q2,q3). ∑ -> Finite number of symbols (a,b,c,d,e). δ ->  Transition Function ( δ,a). q0 ->Initial State. F -> Final States (F⊆Q) where Q is finite number of 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. 