# 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},\mathrm{\Sigma},{\delta}_{1},{I}_{1},{F}_{1})$ and ${A}_{2}=({S}_{2},\mathrm{\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 \mathrm{\Sigma}$, define $\delta $ to be

$$\delta (s,a):=\{\begin{array}{cc}{\delta}_{1}(s,a)\hfill & \text{if}s\in {S}_{1},\hfill \\ {\delta}_{2}(s,a)\hfill & \text{if}s\in {S}_{2}.\hfill \end{array}$$ |

The automaton $A=(S,\mathrm{\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,\mathrm{\Sigma},\delta ,I,F)$ be an automaton. We define the complement ${A}^{\prime}$ of $A$ as the quintuple

$$(S,\mathrm{\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 {\mathrm{\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}={\mathrm{\Sigma}}^{*}-L(A)$, the complement of $L(A)$ in ${\mathrm{\Sigma}}^{*}$.

However, because it is possible that for some $(s,a)$, $\delta (s,a)=\mathrm{\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 |