Pattern recognition is done using finite automata. It adjusts its state in accordance with the input string of symbols. The transition takes place once the desired symbol has been located. The automata can either transition to the next state or remain in the current state at that time. Finite automata can be in either the Accept or Reject state. The automata will accept once the input string has been successfully processed and has reached its finished state.
A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F), where:
Q: finite set of states
∑: finite set of the input symbol
δ: Transition function
q0: initial state
F: final state
Types of Finite Automata:
DFA(deterministic finite automata):
In a DFA, the machine only enters one state for a certain input character. Every state for each input symbol has a corresponding transition function defined. Additionally, DFA does not support null moves, meaning that it cannot alter its state without an input character. It’s crucial to keep in mind that a pattern may have a wide range of DFAs. In general, a DFA with the fewest possible states is favored.
NFA(non-deterministic finite automata) :
NFA and DFA are comparable with the following exceptions:
- Null move is permitted, meaning that it can advance without reading symbols.
- The ability to transmit for a specific input to any number of states.
However, NFA does not gain any power from the aforementioned features. Both are equivalent when compared in terms of power.
Due to the aforementioned extra properties, NFA differs from DFA in terms of transition function.
The transition function allows the NFA to travel to any number of states for any input, including null.
Some Important Points:
- Every DFA is an NFA, but not the other way around.
- Each NFA can be converted into a DFA, and both NFA and DFA have equal power.
- Both DFA and NFA can have many end states.
- The NFA is a more abstract idea.
- In the compiler, DFA is utilized for lexical analysis.
