A finite automata (FA) is the most restricted model of automatic machine. A finite automata is an abstract model of a computer system. As per its defining characteristics is that they have only a finite number of states. Hence, a finite automata can only “count” (that is, maintain a counter, where different states correspond to different values of the counter) a finite number of input scenarios. Hence there has some of the restriction or limitations are as follows;
- The input tape is read only and the only memory it can have is by moving from state to state and since there are finite number of states, a finite automata has memory which is strictly finite.
- The finite automata have only string pattern (regular expression) recognizing power.
- The head movement is restricted in one direction, either from left to right or right to left.
We can modify or enhance the model of finite automata by removing one or more limitation like movement in both direction (Two way finite automata) but these enhancements do not increase the recognizing power of finite automata.
Examples of Limitation of finite auotmata:
There is no finite automaton that recognizes these strings:
- The set of binary strings consisting of an equal number of a’s and b’s.
- The set of strings over ‘(‘ and ‘)’ that have “balanced” parentheses.
The ‘pumping lemma’ can be used to prove that no such FA exists for these examples.
Equivalence of Finite Automata:
Two automata M0 and M1 are said to be equivalent to each other if both accept exactly the same set of input strings. Formally, if two automata M0 and M1 are equivalent then
- If there is a path from the start state of M0 to a final state of M0 labeled M01 M02 … … M0k, there is a path from the start state of M1 to a final state of M1 labeled M01, M02 .. . . . . M0k.
- If there is a path from the start state of M1 to a final state of M1 labeled M11, M12 … . . . . . … . M1k, there is a path from the start state of M0 to a final state of M0 labeled M11, M12,…….. M1k.
Application of Finite Automata (FA):
We have several application based on finite automata and finite state machine. Some are given below;
- A finite automata is highly useful to design Lexical Analyzers.
- A finite automata is useful to design text editors.
- A finite automata is highly useful to design spell checkers.
- A finite automata is useful to design sequential circuit design (Transducer).