6
$\begingroup$

Is there a polynomial time algorithm to determine the number of reachable states in the subset construction of a NFA to a DFA without having to construct the entire DFA?

$\endgroup$
0
3
$\begingroup$

Start with a 3SAT instance $\phi$ on $n$ variables with $m$ clauses $C_1,\ldots,C_m$. For each clause $C_j$, we construct an NFA $A_j$ which reads a binary input string, interpreting its first $n$ symbols as encoding a truth assignment, and checks whether the clause is satisfied. If $C_j$ is satisfied, then on the $(n+1)$'th symbol it branches to $n$ new states.

Now consider an NFA consisting of the NFAs $A_1,\ldots,A_m$ together with an initial state with $\epsilon$-transitions to the starting states of $A_1,\ldots,A_m$ (alternatively, if you allow multiple initial states, you can just put all of them together). If $\phi$ is satisfiable then the number of reachable states in the corresponding DFA will be at least $n^m$, otherwise it will be at most $n^{m-1} + 2^m n + 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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