Application of NFA
NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa. The establishment of such equivalence is important and useful. It is useful because constructing an NFA to recognize a given language is sometimes much easier than constructing a DFA for that language. It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation. For example, it is much easier to prove closure properties of regular languages using NFAs than DFAs.
- The union of two regular languages is regular.
- The concatenation of two regular languages is regular.
- The Kleene closure of a regular language is regular.
Read more about this topic: Nondeterministic Finite Automaton
Famous quotes containing the words application of and/or application:
“We will not be imposed upon by this vast application of forces. We believe that most things will have to be accomplished still by the application called Industry. We are rather pleased, after all, to consider the small private, but both constant and accumulated, force which stands behind every spade in the field. This it is that makes the valleys shine, and the deserts really bloom.”
—Henry David Thoreau (1817–1862)
“It would be disingenuous, however, not to point out that some things are considered as morally certain, that is, as having sufficient certainty for application to ordinary life, even though they may be uncertain in relation to the absolute power of God.”
—René Descartes (1596–1650)