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:
“Most people, no doubt, when they espouse human rights, make their own mental reservations about the proper application of the word “human.””
—Suzanne Lafollette (1893–1983)
“There are very few things impossible in themselves; and we do not want means to conquer difficulties so much as application and resolution in the use of means.”
—François, Duc De La Rochefoucauld (1613–1680)