Answer Happy

Let's compare the running time of two algorithms for the following problem. NFA Union INPUT: two NFAs M and N QUESTION: a DFA P such that L(P) =LM) UL(N) Note that we start with NFAs but we want a DFA as our answer. 1. Algorithm A is: convert M and N separately to DFAs using the subset construction; then do the product construction on the results. 2. Algorithm B is: use Algorithm 3 on M and N, followed by conversion of the resulting NFA, to a DFA. Give the worst-case asymptotic running time of each algorithm, as a function of the number of states on M and N. Is one of them preferable in the sense of asymptotic running time? In your calculations, • charge (29) for a call to the subset construction on an automata with q states charge (9192) for a call to the product construction on automata with 91 and 92 states • charge 0(91 +92) for a call to Algorithm 3 on automata with qı and q2 states