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 $A_{1}=(S_{1},\Sigma,\delta_{1},I_{1},F_{1})$ and $A_{2}=(S_{2},\Sigma,\delta_{2},I_{2},F_{2})$. Let $S,I,F$ be the disjoint unions of $S_{1}$ and $S_{2}$, $I_{1}$ and $I_{2}$, $F_{1}$ and $F_{2}$ respectively. For any $(s,a)\in S\times\Sigma$, define $\delta$ to be

 $\delta(s,a):=\left\{\begin{array}[]{ll}\delta_{1}(s,a)&\textrm{if }s\in S_{1},% \\ \delta_{2}(s,a)&\textrm{if }s\in S_{2}.\end{array}\right.$

The automaton $A=(S,\Sigma,\delta,I,F)$ is called the union of $A_{1}$ and $A_{2}$, and is denoted by $A_{1}\cup A_{2}$. Intuitively, we take the disjoint union of the state diagrams of $A_{1}$ and $A_{2}$, and let it be the state diagram of $A$.

It is easy to see that $L(A_{1}\cup A_{2})=L(A_{1})\cup L(A_{2})$, and that $A_{1}\cup A_{2}$ is equivalent to $A_{2}\cup A_{1}$.

If only one starting state is required, one can modify the definition of $A_{1}\cup A_{2}$ by adding a new state $q$ and setting it as the new start state, then adding an edge from $q$ to each of the states in $I$ with label $\lambda$. The modified $A_{1}\cup A_{2}$ is equivalent to the original $A_{1}\cup A_{2}$. Furthermore, if $A_{1}$ and $A_{2}$ are DFA’s, so is $A_{1}\cup A_{2}$.

Complement of an Automaton

Let $A=(S,\Sigma,\delta,I,F)$ be an automaton. We define the complement $A^{\prime}$ of $A$ as the quintuple

 $(S,\Sigma,\delta,I,F^{\prime})$

where $F^{\prime}=S-F$. It is clear that $A^{\prime}$ is a well-defined automaton. Additionally, $A$ is finite iff $A^{\prime}$ is, and $A$ is deterministic iff $A^{\prime}$ is.

Visually, the state diagram of $A^{\prime}$ is a directed graph whose final nodes are exactly the non-final nodes of $A$.

It is obvious that $(A^{\prime})^{\prime}=A$ and that $A$ is a DFA iff $A^{\prime}$ is.

Suppose $A$ is a DFA. Then it is easy to see that a string $a\in\Sigma^{*}$ is accepted by $A^{\prime}$ precisely when $a$ is rejected by $A$. If $L(A)$ denotes the language consisting of all words accepted by $A$. Then

 $L(A^{\prime})=L(A)^{\prime},$

where $L(A)^{\prime}=\Sigma^{*}-L(A)$, the complement of $L(A)$ in $\Sigma^{*}$.

However, because it is possible that for some $(s,a)$, $\delta(s,a)=\varnothing$, the language accepted by an arbitrary automaton $A^{\prime}$ is in general not $L(A)^{\prime}$.

Intersection of Two Autamata

One may define $A_{1}\cap A_{2}$ to be $(A_{1}^{\prime}\cup A_{2}^{\prime})^{\prime}$. However, defined this way,

 $L(A_{1}\cap A_{2})=L(A_{1})\cap L(A_{2})$

is in general not true.

The way to ensure that the equation above always holds is to define $A_{1}\cap A_{2}$ via the product of $A_{1}$ and $A_{2}$. For more details, see the entry on product of automata.

If both $A_{1}$ and $A_{2}$ are DFA’s, then $A_{1}\cap A_{2}$ is equivalent to $(A_{1}^{\prime}\cup A_{2}^{\prime})^{\prime}$.

Title Boolean operations on automata BooleanOperationsOnAutomata 2013-03-22 18:03:09 2013-03-22 18:03:09 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 03D05 msc 68Q45 complement of an automaton union of automata