# Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $$N$$, design an algorithm that runs in polynomial time such that it determines if $$L(N)$$ is infinite. (Note that converting NFA to DFA is exponential time).

For any DFA, By pumping lemma, I am very sure that the following algorithm works:

T = Upon input <M> (a DFA)
Accept if any state q in DFA has the property:
1. There is a path from starting state to some final state through q
2. There is a (directed) cycle that loops from q back to q.
(Reject if neither property is satisfied)


I intend to prove that this algorithm can be directly applied to NFA. After all, if there is no loop in this NFA, then every accepted string is bounded by the number of states (by pumping lemma). Therefore to make sure the NFA accepts infinite language, a loop is necessary.

Is the thinking correct? Further, what would be the optimal algorithm to see if an NFA generates infinite language?

• What if the cycle contains only epsilon transitions? Nov 18, 2019 at 1:53
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher.
– D.W.
Nov 18, 2019 at 2:58
• Does this answer your question? Determining if an NFA accepts an infinite language in polynomial time
– Stef
May 10 at 15:19

Your algorithm is incorrect. Think about the minimal DFA for $$ab^*c$$.