We are given NFA $A$, which for every input word $w$ has at most 10 runs over word $w$, beginning at the starting state. Show that there exists an algorithm, that converts such NFA to DFA in polynomial time. We don't need that algorithm to work if given automata is not such a NFA.

I think we need to construct DFA with $2^{10}$ states, such that every state would correspond to some run in the NFA - but im not sure about the details.

Any ideas?


1 Answer 1


The main idea is that if the NFA has at most 10 runs over each word, then when reading a word, at any given point the NFA can be in at most 10 states. Therefore in the powerset construction it suffices to consider sets of at most 10 states, of which there are polynomially many.

All remaining details are left to you.


Your Answer

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

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