DFAs were invented to model real world finite state machines in contrast to
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
Some of the content on this page has been obtained from the Deterministic finite state machine page on Wikipedia and used under the CC-BY-SA. - Serving History pages are not affiliated with, or endorsed by, anyone associated with the sources of this content