patternMinor
Determining if an NFA accepts an infinite language in polynomial time
Viewed 0 times
infinitedeterminingacceptsnfapolynomialtimelanguage
Problem
Can we determine in polynomial time if the language accepted by an NFA is infinite?
The case of DFA is simple, but converting an NFA to a DFA may take exponential time.
Also, I ran into this post,
Determine if an NFA accepts infinite language in polynomial time.
But there is no solution.
The case of DFA is simple, but converting an NFA to a DFA may take exponential time.
Also, I ran into this post,
Determine if an NFA accepts infinite language in polynomial time.
But there is no solution.
Solution
Since $\epsilon$-transitions can be removed in polynomial time, let us assume for simplicity that the NFA does not contain any $\epsilon$-transitions (though the argument can be modified to accommodate them).
Suppose that the NFA contains $n$ states, and denote by $L$ the language it accepts. If $L$ is infinite then it contains some word $w$ of length at least $n$. An accepting path of $w$ necessarily passes through the same state twice. This means that there are three states $q_i,q,q_f$, where $q_i$ is initial and $q_f$ is final, and paths $q_i \to^ q$, $q \to^+ q$, and $q \to^ q_f$ (the second one should be non-empty). Conversely, if such states exist, then $L$ is infinite. You can determine whether such states exist in polynomial time, since reachability is in polynomial time.
Suppose that the NFA contains $n$ states, and denote by $L$ the language it accepts. If $L$ is infinite then it contains some word $w$ of length at least $n$. An accepting path of $w$ necessarily passes through the same state twice. This means that there are three states $q_i,q,q_f$, where $q_i$ is initial and $q_f$ is final, and paths $q_i \to^ q$, $q \to^+ q$, and $q \to^ q_f$ (the second one should be non-empty). Conversely, if such states exist, then $L$ is infinite. You can determine whether such states exist in polynomial time, since reachability is in polynomial time.
Context
StackExchange Computer Science Q#151393, answer score: 8
Revisions (0)
No revisions yet.