Editing Nondeterministic finite automaton (section)

==Closure properties==
[[File:Thompson-or.svg|thumb|Composed NFA accepting the union of the languages of some given NFAs {{color|#800000|''N''(''s'')}} and {{color|#008000|''N''(''t'')}}. For an input string ''w'' in the language union, the composed automaton follows an ε-transition from ''q'' to the start state (left colored circle) of an appropriate subautomaton &mdash; {{color|#800000|''N''(''s'')}} or {{color|#008000|''N''(''t'')}} &mdash; which, by following ''w'', may reach an accepting state (right colored circle); from there, state ''f'' can be reached by another ε-transition. Due to the ε-transitions, the composed NFA is properly nondeterministic even if both {{color|#800000|''N''(''s'')}} and {{color|#008000|''N''(''t'')}} were DFAs; vice versa, constructing a DFA for the union language (even of two DFAs) is much more complicated.]]

The set of languages recognized by NFAs is [[closed under]] the following operations. These closure operations are used in [[Thompson's construction algorithm]], which constructs an NFA from any [[regular expression]]. They can also be used to prove that NFAs recognize exactly the [[regular languages]].

*Union (cf. picture); that is, if the language ''L''<sub>1</sub> is accepted by some NFA ''A''<sub>1</sub> and ''L''<sub>2</sub> by some ''A''<sub>2</sub>, then an NFA ''A''<sub>u</sub> can be constructed that accepts the language ''L''<sub>1</sub>∪''L''<sub>2</sub>.
*Intersection; similarly, from ''A''<sub>1</sub> and ''A''<sub>2</sub> an NFA ''A''<sub>i</sub> can be constructed that accepts ''L''<sub>1</sub>∩''L''<sub>2</sub>.
*Concatenation
*Negation; similarly, from ''A''<sub>1</sub> an NFA ''A''<sub>n</sub> can be constructed that accepts Σ<sup>*</sup>\''L''<sub>1</sub>.
*[[Kleene closure]]

Since NFAs are equivalent to nondeterministic finite automaton with ε-moves (NFA-ε), the above closures are proved using closure properties of NFA-ε.