2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.