Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
