Closure Properties
NFAs are said to be closed under a (binary/unary) operator if NFAs recognize the languages that are obtained by applying the operation on the NFA recognizable languages. The NFAs are closed under the following operations.
- Union
- Intersection
- Concatenation
- Negation
- Kleene closure
Since NFAs are equivalent to nondeterministic finite automaton with ε-moves(NFA-ε), the above closures are proved using closure properties of NFA-ε. The above closure properties imply that NFAs only recognize regular languages.
NFAs can be constructed from any regular expression using Thompson's construction algorithm.
Read more about this topic: Nondeterministic Finite Automaton
Famous quotes containing the word properties:
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)