Advantages and Disadvantages
DFAs were invented to model real world finite state machines in contrast to the concept of a Turing machine, which was too general to study properties of real world machines.
DFAs are one of the most practical models of computation, since there is a trivial linear time, constant-space, online algorithm to simulate a DFA on a stream of input. Also, there are efficient algorithms to find a DFA recognizing:
- the complement of the language recognized by a given DFA.
- the union/intersection of the languages recognized by two given DFAs.
Because DFAs can be reduced to a canonical form (minimal DFAs), there are also efficient algorithms to determine:
- whether a DFA accepts any strings
- whether a DFA accepts all strings
- whether two DFAs recognize the same language
- the DFA with a minimum number of states for a particular regular language
DFAs are equivalent in computing power to nondeterministic finite automata (NFAs). This is because, firstly any DFA is also an NFA, so an NFA can do what a DFA can do. Also, given an NFA, using the powerset construction one can build a DFA that recognizes the same language as the NFA, although the DFA could have exponentially larger number of states than the NFA.
On the other hand, finite state automata are of strictly limited power in the languages they can recognize; many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA. The classical example of a simply described language that no DFA can recognize is bracket language, i.e., language that consists of properly paired brackets such as word "()". No DFA can recognize the bracket language because there is no limit to recursion, i.e., one can always embed another pair of brackets inside. It would require an infinite amount of states to recognize. Another simpler example is the language consisting of strings of the form anbn—some finite number of a's, followed by an equal number of b's.
Read more about this topic: Deterministic Finite Automaton
Famous quotes containing the word advantages:
“Can you conceive what it is to native-born American women citizens, accustomed to the advantages of our schools, our churches and the mingling of our social life, to ask over and over again for so simple a thing as that “we, the people,” should mean women as well as men; that our Constitution should mean exactly what it says?”
—Mary F. Eastman, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4 ch. 5, by Susan B. Anthony and Ida Husted Harper (1902)