# Deciding finiteness of regular language is NL-complete?

I've been reading the following Habilitation thesis where the author claims (pg. 29):

... First, deciding whether the language of an NFA is finite is in NL ...

I'm having trouble seeing why this would be true, and can't find a reference anywhere that says as much. Secondly, is this problem also NL-hard? Any help or references would be appreciated.

Let $$\mathcal{A}$$ be an NFA. We say that a state $$q$$ lies on a cycle if there is a non-empty path from $$q$$ to $$q$$ in the graph of $$\mathcal{A}$$. In my answer I assume that the following lemma is true:

The language of an NFA $$\mathcal{A}$$ is infinite if and only if there exists a state $$q'$$ that lies on a cycle such that $$q'$$ is reachable (possibly with an empty path) from some initial state of $$\mathcal{A}$$ and $$q'$$ can reach (possibly with an empty path) some final state of $$\mathcal{A}$$.

Proof. An easy consequence of (i) finiteness of $$\mathcal{A}$$ and (ii) pidgeonhole principle.

As testing reachability can be done in NL, this yields a simple algorithm for checking whether the language of an input $$\mathcal{A}$$ is finite or not.

For the hardness result*, consider a graph $$G$$ with a distinguished source $$s$$ and target $$t$$. We construct NFA $$\mathcal{A}$$ in a way that we turn all the edges of $$G$$ into "a"-letter transitions, make $$s$$ the initial state, and $$t$$ the final state of $$\mathcal{A}$$. Finally we decorate $$t$$ with a self-loop. It is not difficult to see, employing the above lemma, that the language of $$\mathcal{A}$$ is infinite if and only if $$t$$ is reachable from $$s$$. This yields the desired NL-hardness.

*I thank Danis Kuperberg for slightly simplifying my previous reduction.

• you don't really need f and could use directly t instead, with an extra self-loop on it. Nov 2 at 17:57
• Merci, I will update my answer in the morning! Nov 2 at 21:33