Showing that there exists an algorithm, that converts NFA to DFA under some cirumstances

Question

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?

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.