<p>Since the other answer makes it sound as if it were not obvious, let me point out that the problem is computable in PSPACE. First, we observe:</p>
<blockquote>
<p><strong>Lemma.</strong> For any NFA <span class="math-container">$A$</span> with <span class="math-container">$n$</span> states, the following are equivalent:</p>
<ol>
<li><span class="math-container">$L(A)$</span> is infinite.</li>
<li><span class="math-container">$A$</span> accepts a word of length <span class="math-container">$\ge n$</span>.</li>
<li>There is an accepting run of <span class="math-container">$A$</span> that goes through some state twice.</li>
</ol>
<p>Either condition 2 or 3 can be checked in NL.</p>
</blockquote>
<p><strong>Proof:</strong> 1 → 2 is obvious. 2 → 3: An accepting run of length <span class="math-container">$\ge n$</span> (hence with <span class="math-container">$\ge n+1$</span> states, including the starting and final states) must repeat some state by the pigeonhole principle. 3 → 1: We can repeat the part of the accepting run between two occurrences of the same state as many times as we want, yielding arbitrary long accepted words.</p>
<blockquote>
<p><strong>Corollary.</strong> Cofiniteness for NFA can be checked in <span class="math-container">$\mathrm{coNPSPACE=PSPACE}$</span>.</p>
</blockquote>
<p><strong>Proof:</strong> Determinize the automaton using the powerset construction, flip accepting and rejecting states, and apply the Lemma to the result. It is not necessary to construct the whole powerset automaton in advance—we can just guess transitions on the fly, storing only a representation of the current state (i.e., a subset of the original automaton), hence the needed space is only <span class="math-container">$O(n)$</span> (for a nondeterministic algorithm).</p>

CC BY-SA 4.0
2024-03-23T08:27:04.733Z
Thanks for clarifying this!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-03-23T08:04:30.897Z
2024-03-23T08:21:50.897Z
2024-03-23T08:21:50.897Z
Emil Jeřábek
<p><strong>Lemma 1.</strong> <em>Determining whether a given NFA is cofinite is PSPACE-hard.</em></p>
<p><em>Proof.</em>  The proof is by an easy reduction from the PSPACE-complete problem of determining whether a given NFA is universal.  The reduction is similar to one <a href="https://cs.stackexchange.com/a/153723/4678">here</a>.
Given an NFA <span class="math-container">$N$</span>,
the reduction outputs (in poly-time) the NFA <span class="math-container">$N'$</span> whose language
is
<span class="math-container">$$L(N') = (L(N) \cdot \#)^* \cdot L(N),$$</span>
where <span class="math-container">$\#$</span> is a new letter added to the alphabet of <span class="math-container">$N$</span>.</p>
<p>Given <span class="math-container">$N$</span> such an NFA <span class="math-container">$N'$</span> can be constructed in poly time.</p>
<p>Now suppose that <span class="math-container">$N$</span> is universal.
Letting <span class="math-container">$\Sigma$</span> be the alphabet of <span class="math-container">$N$</span>,
any string <span class="math-container">$x$</span> over the alphabet <span class="math-container">$\Sigma' = \Sigma\cup\{\#\}$</span> of <span class="math-container">$N'$</span> is of the form
<span class="math-container">$$x = w_1 \# w_2 \# \cdots \# w_k$$</span>
where <span class="math-container">$w_i\in \Sigma^*$</span>.
Such a string <span class="math-container">$x$</span> is in <span class="math-container">$L(N')$</span>
iff each <span class="math-container">$w_i$</span> is in <span class="math-container">$L(N)$</span>.
So, if <span class="math-container">$N$</span> is universal, then every such string <span class="math-container">$x$</span> is in <span class="math-container">$L(N')$</span>,
so <span class="math-container">$L(N')$</span> is universal and cofinite.</p>
<p>On the other hand, if <span class="math-container">$N$</span> is not universal,
then some string <span class="math-container">$w$</span> is not in <span class="math-container">$L(N)$</span>,
so every <span class="math-container">$x$</span> (as described above) with any <span class="math-container">$w_i = w$</span>
is not in <span class="math-container">$L(N')$</span>.  There are infinitely many such <span class="math-container">$x$</span>,
so the complement of <span class="math-container">$L(N')$</span> is infinite.
That is, <span class="math-container">$N'$</span> is not cofinite.</p>
<p>So <span class="math-container">$N'$</span> is cofinite iff <span class="math-container">$N$</span> is universal, the reduction is correct,
and determining whether <span class="math-container">$N'$</span> is cofinite is PSPACE-hard. <span class="math-container">$~~~\Box$</span></p>
<p>As Emil details in <a href="https://cstheory.stackexchange.com/a/54094/8237">another answer</a>,
the problem is in PSPACE,
by a proof similar to <a href="https://cs.stackexchange.com/questions/24390/why-is-the-set-of-nfa-that-accept-all-words-in-co-npspace">the one</a> that shows universality is in PSPACE.  So the problem is PSPACE-complete.</p>

CC BY-SA 4.0
2024-03-23T08:27:19.983Z
Ah, that's a nice argument, thanks! :)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-03-22T21:42:09.263Z
2024-03-23T14:04:03.183Z
2024-03-23T14:04:03.183Z
Neal Young
<p>What is the complexity, given as input an NFA, of determining if it is cofinite (i.e., the complement of its language is finite)?</p>
<p>Surely this must be known but I can't find a reference. Note that the problem of determining if an NFA is universal is PSPACE-complete, but I don't see an obvious reduction.</p>

CC BY-SA 4.0
2024-03-22T20:18:30.070Z
Determining if the language is finite is a simple reachability problem, thus computable in NL, and consequently cofiniteness is computable in PSPACE by applying this to the complement. So I suppose the problem is whether it is PSPACE-hard, right?
Emil Jeřábek
CC BY-SA 4.0
2024-03-25T07:42:31.110Z
Yes, thanks for your answer! (I accepted Neal's answer as this is the less "obvious" direction, but I would have accepted both if I could)
M.Monet
<reference-request><nfa>
Complexity of NFA cofiniteness
M.Monet
# Complexity of NFA cofiniteness

(Asked by: username_0 on 2024-03-22)

What is the complexity, given as input an NFA, of determining if it is cofinite (i.e., the complement of its language is finite)?

Surely this must be known but I can't find a reference. Note that the problem of determining if an NFA is universal is PSPACE-complete, but I don't see an obvious reduction.

**Tags:** reference-request, nfa
> **Comments:**
> **username_1**: Determining if the language is finite is a simple reachability problem, thus computable in NL, and consequently cofiniteness is computable in PSPACE by applying this to the complement. So I suppose the problem is whether it is PSPACE-hard, right?  
> **username_0**: Yes, thanks for your answer! (I accepted Neal's answer as this is the less "obvious" direction, but I would have accepted both if I could)  

---

## 2 answers

### Answer by username_3 on 2024-03-22. Score: 14 | Accepted answer

**Lemma 1.** *Determining whether a given NFA is cofinite is PSPACE-hard.*

*Proof.* The proof is by an easy reduction from the PSPACE-complete problem of determining whether a given NFA is universal. The reduction is similar to one [here](https://cs.stackexchange.com/a/153723/4678).
Given an NFA $N$,
the reduction outputs (in poly-time) the NFA $N'$ whose language
is
$$L(N') = (L(N) \cdot \#)^\* \cdot L(N),$$
where $\#$ is a new letter added to the alphabet of $N$.

Given $N$ such an NFA $N'$ can be constructed in poly time.

Now suppose that $N$ is universal.
Letting $\Sigma$ be the alphabet of $N$,
any string $x$ over the alphabet $\Sigma' = \Sigma\cup\{\#\}$ of $N'$ is of the form
$$x = w\_1 \# w\_2 \# \cdots \# w\_k$$
where $w\_i\in \Sigma^\*$.
Such a string $x$ is in $L(N')$
iff each $w\_i$ is in $L(N)$.
So, if $N$ is universal, then every such string $x$ is in $L(N')$,
so $L(N')$ is universal and cofinite.

On the other hand, if $N$ is not universal,
then some string $w$ is not in $L(N)$,
so every $x$ (as described above) with any $w\_i = w$
is not in $L(N')$. There are infinitely many such $x$,
so the complement of $L(N')$ is infinite.
That is, $N'$ is not cofinite.

So $N'$ is cofinite iff $N$ is universal, the reduction is correct,
and determining whether $N'$ is cofinite is PSPACE-hard. $~~~\Box$

As Emil details in [another answer](https://cstheory.stackexchange.com/a/54094/8237),
the problem is in PSPACE,
by a proof similar to [the one](https://cs.stackexchange.com/questions/24390/why-is-the-set-of-nfa-that-accept-all-words-in-co-npspace) that shows universality is in PSPACE. So the problem is PSPACE-complete.

> **Comments:**
> **username_2**: Ah, that's a nice argument, thanks! :)  

---

### Answer by username_1 on 2024-03-23. Score: 8

Since the other answer makes it sound as if it were not obvious, let me point out that the problem is computable in PSPACE. First, we observe:

> **Lemma.** For any NFA $A$ with $n$ states, the following are equivalent:
>
> 1. $L(A)$ is infinite.
> 2. $A$ accepts a word of length $\ge n$.
> 3. There is an accepting run of $A$ that goes through some state twice.
>
> Either condition 2 or 3 can be checked in NL.

**Proof:** 1 → 2 is obvious. 2 → 3: An accepting run of length $\ge n$ (hence with $\ge n+1$ states, including the starting and final states) must repeat some state by the pigeonhole principle. 3 → 1: We can repeat the part of the accepting run between two occurrences of the same state as many times as we want, yielding arbitrary long accepted words.

> **Corollary.** Cofiniteness for NFA can be checked in $\mathrm{coNPSPACE=PSPACE}$.

**Proof:** Determinize the automaton using the powerset construction, flip accepting and rejecting states, and apply the Lemma to the result. It is not necessary to construct the whole powerset automaton in advance—we can just guess transitions on the fly, storing only a representation of the current state (i.e., a subset of the original automaton), hence the needed space is only $O(n)$ (for a nondeterministic algorithm).

> **Comments:**
> **username_2**: Thanks for clarifying this!  

---

