| DESCRIPTION | 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. ... If ... and ... . Let ... be the disjoint unions of ... and ... , ... and ... , ... and ... respectively. For any ... , define delta 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 <i>A</i>. 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 <i>q</i> and setting it as the new start state, then adding an edge from <i>q</i> to each of the states in <i>I</i> with label lambda. The modified ... is equivalent to the original ... . Furthermore, if ... and ... are DFA's, so is ... . ... Let ... be an automaton. We define the complement ... of <i>A</i> as the quintuple ... where ... . It is clear that ... is a well-defined automaton. Additionally, <i>A</i> is finite iff ... is, and <i>A</i> is deterministic iff ... is. Visually, the state diagram of ... is a directed graph whose final nodes are exactly the non-final nodes of <i>A</i>. It is obvious that ... and that <i>A</i> is a DFA iff ... is. Suppose <i>A</i> is a DFA. Then it is easy to see that a string ... is accepted by ... precisely when <i>a</i> is rejected by <i>A</i>. If ... denotes the language consisting of all words accepted by <i>A</i>. 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 ... . ... One may define ... to be ... . However, defined this way, ... is in general not true. The way to ensure that the equation above always holds is to define ... via the product of ... and ... . For more details, see the entry on product of automata. If both ... and ... are DFA's, then ... is equivalent to ... . |
