Introduction To Finite Automata
Finite Automata (FA) is a machine which accepts all the regular languages. It is used to recognize the patterns. It is also called finite state machine.
Working Of Finite Automata
- The finite automata machine contains five tuple or elements.
- It has some finite states and rules for moving from one state to another but it depends upon the given input symbol.
Basic diagram is given below
A Finite Automata can be defined through its 5 tuples { Q, Σ, q, F, δ }. Where
- Q : Finite set of states.
- Σ : set of Input Symbols.
- q : Initial state.
- F : set of Final States.
- δ : Transition Function.
Types Of Finite Automata
FA is characterized into two types:
1) Deterministic Finite Automata (DFA)
- In a DFA, for a particular input symbol, the machine goes to one state only.
- In DFA null (ε) move is not allowed. It means state cannot change without a input symbol.
DFA contains 5 tuples {Q, Σ, q, F, δ}.
Q : set of all states.
Σ : set of input symbols.
q : Initial state.
F : set of final state.
δ : Transition Function, δ : Q X Σ –> Q.
2) Nondeterministic Finite Automata(NFA)
- NFA is similar to DFA except the Null (or ε) move. In NFA Null move is allowed. It means state can change without a input symbol.
- NFA also has similar 5 tuples {Q, Σ, q, F, δ} like DFA except transition function. It NFA Transition Function is given below
δ: Q X (Σ U ε ) –> 2 ^ Q.
Some important points about DFA and NFA
- Every DFA is NFA, but NFA is not DFA.
- In NFA and DFA, there can be multiple final states.
- DFA is used in Lexical Analysis in Compiler.
- NFA mostly used as theoretical concept.