0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What if the cycle contains only epsilon transitions? $\endgroup$ – Draconis Nov 18 '19 at 1:53
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 18 '19 at 2:58
0
$\begingroup$

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

Related: Do self-loops in DFA cause infinite languages?, Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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