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
Canonical name	BooleanOperationsOnAutomata
Date of creation	2013-03-22 18:03:09
Last modified on	2013-03-22 18:03:09
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03D05
Classification	msc 68Q45
Defines	complement of an automaton
Defines	union of automata