# Number of accepting path of a non deterministic automaton

I have a question that seems to me really natural and have probably already been studied. But keyword search on this site or google does not seems to help me to find any relevent paper.

I have got a finite non deterministic automaton $A$ over an alphabet $\alpha$ without epsilon-transition.

What can I tell about the number of different path the automaton could take for accepting a word ? In particular, I want to know if this number is bounded, or if for every $c$ I can find a word $w_c$ that is accepted in at least $c$ different way by the automaton.

Right now, I can find some necessary, and some sufficient condition, but not any necessary and sufficient condition, for the number to be unbounded

By clarity, I'll define the way I cound the number of accepting path. Let $w\in\alpha^*$ and $q$ a state, I can define the number of path to $q$ by inuction on $|w|$ by $N(\epsilon,q)=1$ if $q\in I$ else $0$, where $I$ is the set of initial state and $F$ of final state. $N(ws,q)=\sum_{q'\in Q\atop \delta(q',s)=q}N(w,q')$.

Then the number of path is $\sum_{q \in F}N(w,q)$.

• I'm not sure I understand exactly the question. Do you want to find an algorithm that get as input a TM $N$ and decides whether the number of accepting paths is bounded for every input to $N$? I guess that this problem is undecidable. – Igor Shinkar May 18 '13 at 3:34

An NFA has a polynomial number of runs on a word $w$ iff for every state $q$, there is at most one cycle from $q$ to itself on every word $x\in \Sigma^*$. See this for details.