retagged by
708 views

1 Answer

Best answer
5 votes
5 votes

An NFA accepts an infinite language if and only if there is a (directed) path from the initial to an accepting state which contains at least one state more than once.

So, just check for existence of cycle in the graph corresponding to the NFA starting with the start state - BFS can be used - $O(V+E) = O(|Z| n)$ where $Z$ is the alphabet set and $n$ is the no. of states in the NFA. 

Since we have an algorithm (no need to worry about the time complexity), our decision problem is answered - "yes" is its answer. Or it is decidable to check if a given regular language is finite. More precisely it is decidable in polynomial time whether a given regular language is finite (the problem is not only decidable but also belongs to complexity class $P$).


 

edited by

Related questions

4 votes
4 votes
3 answers
2
2 votes
2 votes
2 answers
3
Na462 asked Sep 13, 2018
669 views
Is the given Grammer represent a regular language ?S->AaBA->aC | epsilonB->aB | bB | epsilonC->aCb | epsilon
5 votes
5 votes
2 answers
4
Akanksha Kesarwani asked Dec 13, 2015
5,275 views
Which of the following language is $CFL$?a. $\{a^mb^nc^n\;|\;m!=n\}$b. $\{a^mb^nc^k\;|\;if\,(m=n)\,then\,(n!=k)\}$c. $\{a^mb^nc^k\;|\;m>n\;or\;n<k\}$d. None of these