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:
“By an application of the theory of relativity to the taste of readers, to-day in Germany I am called a German man of science, and in England I am represented as a Swiss Jew. If I come to be regarded as a bête noire the descriptions will be reversed, and I shall become a Swiss Jew for the Germans and a German man of science for the English!”
—Albert Einstein (1879–1955)
“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)