Finite Automata

The Finite Automata is the simplest machine which is used to recognize patterns. It has a finite set of states with which it accepts or rejects strings. It is an abstract machine which has five elements or tuples. It is good for devices which have an extremely limited amount of memory. It has a set of states and rules for moving from one state to another, but it relies upon the applied input symbol. It has finite memory and an input tape. The machine accepts the input if it is in the accepting state at the end of the string; otherwise, it rejects the input.

Concepts of Finite Automata

Here, let's understand the basic concept behind finite automata through an example-

Suppose you want to recognize the word 'Yes' as an input string in a program. Then the steps of the program something like this-

• Initialization
• Looking for the first word, i.e., "Y" and recognized "Y"
• Looking for the next word, i.e., "e" and recognized "Ye"
• Looking for the next word, i.e., "s" and recognized "Yes"

Real life example of Finite Automata

An automatic door is a good example of finite automata. It is sensing a person's appearance and accordingly open & close the door. It has two states OPEN and CLOSE and the controller works on the input signals. If it receives input either from FRONT or REAR or from both, it opens the door long enough to pass the person and then close the door.

Formal Definition of Finite Automata

A finite automata has several parts. It has a set of states and rules for going from one state to another, depending on the input symbol. The list of five objects is sets of states, start state, input alphabet, rules for moving and accept state. In a mathematical language, a list of five objects is obtained called five tuples-

Q, ∑, δ, q0, F

Q - Finite set of states,
∑ - alphabet of input symbols,
δ: Q × ∑ → Q - transition function,
q0 (q0 ∈ Q) - initial state,
F - A set of final state (F ⊆ Q).

The finite automata are generally represented by the transition diagram having the following states.

	State
	Transition
	Start State
	Accepting State

State Diagram of Finite Automata

Suppose, here is a state diagram of finite automaton M.

The finite automata M is written as-

M = (Q, ∑, δ, q0, F)

where,

Q = {q0, q1, q2},
∑ = {0,1},

δ is described as -

			0	1
		q0	q1	q0
		q1	q1	q2
		q2	q1	q1

q0, is the start state,

and

F = {q1}, is the final state

Classification of Finite Automata

Finite Automata is classified into two types -

• Deterministic Finite Automata (DFA)
• Nondeterministic Finite Automata(NFA)