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

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

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

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

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

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

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