Editing Deterministic finite automaton (section)

==Closure properties==
[[File:Intersection1.png|thumb|400px|The upper left automaton recognizes the language of all binary strings containing at least one occurrence of "00". The lower right automaton recognizes all binary strings with an even number of "1". The lower left automaton is obtained as product of the former two, it recognizes the intersection of both languages.]]
If DFAs recognize the languages that are obtained by applying an operation on the DFA recognizable languages then DFAs are said to be [[closed under]] the operation. The DFAs are closed under the following operations.

{{columns-list|colwidth=30em|
*Union
*Intersection{{sfn|Hopcroft|Ullman|1979|pp=59–60}} (see picture)
*Concatenation
*[[Complementation of automata#With deterministic finite automata|Complement]]
*[[Kleene closure]]
*Reversal<ref name=rose/>
*Quotient<ref name=rose>{{cite journal
 | last = Rose | first = Gene F.
 | doi = 10.1016/S0022-0000(68)80029-7
 | issue = 2
 | journal = [[Journal of Computer and System Sciences]]
 | pages = 148–168
 | title = Closures which Preserve Finiteness in Families of Languages
 | volume = 2
 | year = 1968}}</ref>
*Substitution<ref name=spanier>{{cite journal
 | last = Spanier | first = E.
 | doi = 10.1080/00029890.1969.12000214
 | journal = American Mathematical Monthly
 | jstor = 2316423
 | mr = 241205
 | pages = 335–342
 | title = Grammars and languages
 | volume = 76
 | year = 1969| issue = 4
 }}</ref>
*Homomorphism<ref name=rose/><ref name=spanier/>
}}

For each operation, an optimal construction with respect to the number of states has been determined in [[state complexity]] research.
Since DFAs are [[Powerset construction|equivalent]] to [[nondeterministic finite automaton|nondeterministic finite automata]] (NFA), these closures may also be proved using closure properties of NFA.