-1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.