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’.
- 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
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.
At First it received 1 and transition to q1
Then we received 0 and transition to q3
Then we received a 1 and transition to q2.
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.
First automata reads a 1, and automata goes to q1.
At q1, automata gets another 1 and goes back to q0 which is accepting state.
At q0, receives a 0 and goes to q2 state.
Finally, automata receives a 0 and goes to q0 final state.
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.