Consider an NFA on n states. Is it possible to determine whether it is empty accepts all strings in poly(n) time?
Suppose the NFA above has an equivalent DFA on d states. Is it possible to construct this DFA in poly(n,d) time?
|
2 | Fixed question | ||
|
|
||||
|
|
1 |
|
||
Emptiness and determinization of NFAsConsider an NFA on n states. Is it possible to determine whether it is empty in poly(n) time? Suppose the NFA above has an equivalent DFA on d states. Is it possible to construct this DFA in poly(n,d) time?
|
||||
