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:
“The human mind is capable of excitement without the application of gross and violent stimulants; and he must have a very faint perception of its beauty and dignity who does not know this.”
—William Wordsworth (1770–1850)
“It is known that Whistler when asked how long it took him to paint one of his “nocturnes” answered: “All of my life.” With the same rigor he could have said that all of the centuries that preceded the moment when he painted were necessary. From that correct application of the law of causality it follows that the slightest event presupposes the inconceivable universe and, conversely, that the universe needs even the slightest of events.”
—Jorge Luis Borges (1899–1986)