<p>You mean the worst-case complexity of computing NFAs accepting <span class="math-container">$L(\mathcal{A}) \cup L(\mathcal{B})$</span> and <span class="math-container">$L(\mathcal{A}) \cap L(\mathcal{B})$</span>?</p>
<p>For union it's easy to achieve <span class="math-container">$O\left(|Q_A| + |Q_B|\right)$</span> as we need to add new initial state <span class="math-container">$q_{\ast}$</span> and add transitions of kind <span class="math-container">$(q_{\ast}, a, q)$</span> whether <span class="math-container">$(q_{i_A}, a, q) \in \Delta_A$</span> or <span class="math-container">$(q_{i_B}, a, q) \in \Delta_B$</span>. (If you allow <span class="math-container">$\epsilon$</span>-transitions, you may obtain <span class="math-container">$O(1)$</span>.)</p>
<p>For intersection we can achieve <span class="math-container">$O(2^{|Q_A| + |Q_B|})$</span> by constructing two DFAs <span class="math-container">$\mathcal{A}'$</span> and <span class="math-container">$\mathcal{B}'$</span> equivalent to <span class="math-container">$\mathcal{A}$</span> and <span class="math-container">$\mathcal{B}$</span> and then considering their Cartesian product.</p>

CC BY-SA 4.0
2021-01-17T17:37:09.240Z
The product construction should work just fine for computing the intersection.  There is no need to convert the NFA's to DFA's.
Michael Wehar
CC BY-SA 4.0
2021-01-17T16:34:31.143Z
2021-01-17T16:34:31.143Z
DG_
<p>Assume that <span class="math-container">$\mathcal{A} = (Q_A, \Sigma, \Delta_A, q_{i_A}, F_A)$</span> and <span class="math-container">$\mathcal{B} = (Q_B, \Sigma, \Delta_B, q_{i_B}, F_B)$</span> are two NFAs. What is the worst-case time complexity of computing <span class="math-container">$\mathcal{A} \cup \mathcal{B}$</span> and <span class="math-container">$\mathcal{A} \cap \mathcal{B}$</span>?</p>

<automata-theory><time-complexity><regular-language>
What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?
greps
# What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?

(Asked by: username_0 on 2021-01-07)

Assume that $\mathcal{A} = (Q\_A, \Sigma, \Delta\_A, q\_{i\_A}, F\_A)$ and $\mathcal{B} = (Q\_B, \Sigma, \Delta\_B, q\_{i\_B}, F\_B)$ are two NFAs. What is the worst-case time complexity of computing $\mathcal{A} \cup \mathcal{B}$ and $\mathcal{A} \cap \mathcal{B}$?

**Tags:** automata-theory, time-complexity, regular-language

---

## 1 answers

### Answer by username_1 on 2021-01-17. Score: 1

You mean the worst-case complexity of computing NFAs accepting $L(\mathcal{A}) \cup L(\mathcal{B})$ and $L(\mathcal{A}) \cap L(\mathcal{B})$?

For union it's easy to achieve $O\left(|Q\_A| + |Q\_B|\right)$ as we need to add new initial state $q\_{\ast}$ and add transitions of kind $(q\_{\ast}, a, q)$ whether $(q\_{i\_A}, a, q) \in \Delta\_A$ or $(q\_{i\_B}, a, q) \in \Delta\_B$. (If you allow $\epsilon$-transitions, you may obtain $O(1)$.)

For intersection we can achieve $O(2^{|Q\_A| + |Q\_B|})$ by constructing two DFAs $\mathcal{A}'$ and $\mathcal{B}'$ equivalent to $\mathcal{A}$ and $\mathcal{B}$ and then considering their Cartesian product.

> **Comments:**
> **username_2**: The product construction should work just fine for computing the intersection.  There is no need to convert the NFA's to DFA's.  

---

