Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Consider an NFA on n states. Is it possible to determine whether it is emptyaccepts 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?
Consider an NFA on n states. Is it possible to determine whether it is empty in poly(n) time?
Consider an NFA on n states. Is it possible to determine whether it accepts all strings in poly(n) time?
