# What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?

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

## 1 Answer

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.

• 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 Jan 17 at 17:37