To see this, let E(p) be the set of states reachable from p without reading any symbols, i.e., via transitions labeled by the empty string. Then E(p) is computed in polytime w.r.t. the total number

of states. Indeed, we keep the current set of reachable states, initially {p}, and for each such state and for each applicable transition we add the new state to the set if it is not already there. The size of the set is <= m, the number of all transitions is <= m^2, and the number of iterations where a new state is added is <= m. (See p. 69 of Lewis and Papadimitriou.)

Now, given an input string

, we again keep the current set of reachable states S. Given the next symbol

from

, we add {E(q) | (p, a, q) is a transition and p ∊ S} to S. The size of S is <= m, so the total time required is

for some

. (See p. 106 of the book.)