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.
-
3$\begingroup$ The product construction should work just fine for computing the intersection. There is no need to convert the NFA's to DFA's. $\endgroup$ Jan 17, 2021 at 17:37