3
$\begingroup$

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.

$\endgroup$

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

An NFA (with $\epsilon$-moves or not) can be viewed naturally as a directed multi-graph. We will use "state" and "node" interchangeably.

Whether an NFA accepts an infinite language is the same as whether there is a path from the initial state to an accepting state that contains at least one state that is a part of a cycle. Here we consider a self-loop as a cycle. See Yuval's answer for a simple proof.

An algorithm in polynomial time

A DFS from the initial state can determine all states that are reachable from the initial state.
A DFS from each state can determine whether the NFA can reach an accepting state from that state.
For each state, we can use a depth-first-search (DFS) to determine whether it is a part of a cycle.
If there is a state which is reachable from the initial state and from which the NFA can reach an accepting state and which is a part of a cycle, the answer is Yes. Otherwise, the answer is No.

An algorithm in linear time

For every ordered nodes $s_1$ and $s_2$ in the directed multi-graph, we can replace all edges from $s_1$ to $s_2$ by a single edge from $s_1$ to $s_2$, which transforms the directed multi-graph into a directed graph without multi-edges (with self-loops possibly). This transformation does not affect paths nor cycles.

Call the transformed graph $H$.

A DFS on $H$ from the initial state can mark all reachable accepting states. Another DFS on $H$ starting from an additional node, "the super-accepting state" that is connected from all accepting states, treating each edge backwards, can mark all states from which the NFA can reach an accepting state. A state is marked by both DFS iff there is a path from the initial state to an accepting state that contains that state.

A state is a part of a cycle iff it is a part of a cyclic strongly connected components (SCCs). An SCC is called cyclic if it contains a cycle, i.e., if it contains either a self-loop or more than one node. We can adapt easily any one of common linear-time algorithms that find all SCCs to find all cyclic SCCs with the same time-complexity.

If there is a state that is marked by both DFS and is part of a cyclic SCC, the answer is Yes. Otherwise the answer is No.

Since each of the transformation, both DFSs, the adapted SCC-finding algorithm and the final check runs in linear time, the entire algorithm runs in linear time.

$\endgroup$
0

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.