Boolean operations on automata
A Boolean operation is any one of the three set-theoretic operations: union, intersection, and complementation. Boolean operations on automata are operations defined on automata resembling those from set theory.
Union of Two Automata
If and . Let be the disjoint unions of and , and , and respectively. For any , define to be
The automaton is called the union of and , and is denoted by . Intuitively, we take the disjoint union of the state diagrams of and , and let it be the state diagram of .
It is easy to see that , and that is equivalent to .
If only one starting state is required, one can modify the definition of by adding a new state and setting it as the new start state, then adding an edge from to each of the states in with label . The modified is equivalent to the original . Furthermore, if and are DFA’s, so is .
Complement of an Automaton
Let be an automaton. We define the complement of as the quintuple
where . It is clear that is a well-defined automaton. Additionally, is finite iff is, and is deterministic iff is.
Visually, the state diagram of is a directed graph whose final nodes are exactly the non-final nodes of .
It is obvious that and that is a DFA iff is.
Suppose is a DFA. Then it is easy to see that a string is accepted by precisely when is rejected by . If denotes the language consisting of all words accepted by . Then
where , the complement of in .
However, because it is possible that for some , , the language accepted by an arbitrary automaton is in general not .
Intersection of Two Autamata
One may define to be . However, defined this way,
is in general not true.
If both and are DFA’s, then is equivalent to .
|Title||Boolean operations on automata|
|Date of creation||2013-03-22 18:03:09|
|Last modified on||2013-03-22 18:03:09|
|Last modified by||CWoo (3771)|
|Defines||complement of an automaton|
|Defines||union of automata|