Finite automata are use to recognize patterns.
It takes the string of symbol as input and changes its state accordingly. When the desiring symbol is search, then the transition occurs.
At the time of transition, the automata can either move to the next state or stay in the same state.
Finite automata have two states, Accept state or Reject state. When the input string is processing successfully, and the automata reached its final state,
then it will accept.
Finite Automata Model:
A finite automaton is a collection and machine of 5-tuple (Q, ∑, δ, q0, F), where:
- Q: finite set of states
- ∑: finite set of the input symbol
- q0: initial state
- F: final state
- δ: Transition function
Input tape: It is a linear tape having some number of cells. Each input symbol is place in each cell.
Finite control: The finite control decides the next state on receiving particular input from input tape.The tape reader reads the cells one to one from left to right, and at a time only one input symbol is read.
Types of Automata:
There are two types of finite automata:
- DFA(deterministic)
- NFA(non-deterministic)
1. DFA
DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. In the DFA, the machine goes to one state only for a particular input character. DFA does not accept the null move.
2. NFA
NFA stands for non-deterministic automata. It is used to transmit any number of states for a particular input. It can accept the null move.
Some important points about DFA and NFA:
Every DFA is NFA, but NFA is not DFA.
There can be multiple final states in both NFA and DFA.
DFA is used in Lexical Analysis in Compiler.
NFA is more of a theoretical concept.
Application of Finite Automata (FA):
We have several application based on finite automata and finite state machine. Some are given below;
It is highly useful to design Lexical Analyzers.
An automata is useful to design text editors.
This automata is highly useful to design spell checkers.
For this automata is useful to design sequential circuit design (Transducer).
