## You are here

HomeBoolean operations on automata

## Primary tabs

# 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}}$.

## Mathematics Subject Classification

03D05*no label found*68Q45

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections