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:
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)