<p>See this paper:
Counting the size of regular sequences of given length is #P-complete:
S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting
and random generation of strings in regular languages.
In ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 551–557, 1995.</p>

CC BY-SA 3.0
2016-12-19T16:36:46.070Z
2016-12-19T16:36:46.070Z
Miklós István
<p>Almost the exact same question was asked <a href="https://cstheory.stackexchange.com/questions/8200/counting-words-accepted-by-a-regular-grammar">here</a>, but nobody proved or cited its #P-completeness! I found this question because I proved it is #P-complete (proof below), and the proof was <em>trivial</em>, but I couldn't find it anywhere on the web or in the discussion on that question! (One person commented "I suspect it is #P-complete".) So either my proof is wrong, which you can judge for yourself, or the result is novel, which I would think is highly unlikely. Which is it?</p>

<hr>

<p><strong>Proof:</strong></p>

<p>Consider the set of regular expressions formed by the union and concatenation of symbols from $(\Sigma\cup{.})$, where $\Sigma$ is an alphabet and $.$ is a symbol for any $l\in\Sigma$. I will show that #SAT reduces in $O(mn)$ time to counting the number of strings that satisfy such a regex, where $m$ is the number of clauses and $n$ is the number of variables in the given formula $\varphi$.</p>

<p>The reduction is very simple. First, reduce #SAT to #UNSAT by noting that if $\varphi$ has $n$ variables, then $\#\text{SAT}(\varphi) = 2^n - \#\text{UNSAT}(\varphi)$. So now we have to count the number of falsifying assignments of the variables of $\varphi$.</p>

<p>To falsify $\varphi$, it suffices to falsify just one clause. We therefore want to find 
$$\left|\bigcup \limits_{C\in\varphi}F(C)\right|$$
where $F(C)$ is the set of assignments of literals that falsify $C$. </p>

<p>We thus write a regex representing the language of falsifying assignments for each clause. Using $\Sigma = \{0,1\}$, and letting $r_i$ be the $i^{th}$ symbol of a regex $r$, the regex for the language of assignments that falsify a clause $C$ is
$$
r_i = \begin{cases}
         0 &amp; \text{if } x_i\in C \\
         1 &amp; \text{if } \overline{x_i}\in C \\
         . &amp; \text{otherwise}
      \end{cases}
$$</p>

<p>We then take the union of the regexes for each clause $C\in\varphi$. For example, if $\varphi = (x_1\vee \overline{x_2}\vee x_3) \wedge (x_1\vee x_3\vee \overline{x_4})\wedge (\overline{x_1}\vee \overline{x_4})$ we would have $r = $<code>010.|0.01|1..1</code>, where <code>|</code> denotes union. </p>

<p>The construction yields a union of $m$ strings, each of $n$ symbols. Thus the reduction takes $O(mn)$ time and the size of the regex-counting instance is polynomial in the size of the formula. Further, any regular expression that uses only concatenation, dot, and union represents a finite regular language (specifically, there is no Kleene star). So since we can solve #SAT by counting strings that satisfy such a regex, we can say that counting the words in a finite language is #P-complete.</p>

CC BY-SA 3.0
2015-09-08T07:38:58.390Z
"Almost the exact same question" they are very different. Your languages are finite.
Chao Xu
CC BY-SA 3.0
2015-09-08T11:14:12.277Z
@ChaoXu: but if it is #P-complete for finite languages, then  the problem "Given an NFA, count the number of matching words of length $k$" (the linked problem) is #P-complete when $k$ is given in unary ... so the two questions are not so different. However it seems a known result (see for example: http://dl.acm.org/citation.cfm?id=313803). Note that the problem is in P for *deterministic* finite automata.
Marzio De Biasi
CC BY-SA 3.0
2015-09-08T18:10:46.857Z
@ChaoXu: How? I actually spent awhile thinking about this issue before Marzio's comment which is (I think) completely right.
Huck Bennett
CC BY-SA 3.0
2015-09-08T18:13:08.553Z
@ChaoXu its equivalent, just take $n$ larger than the largest word in the language. In my problem $n$ is known as the number of variables of $\varphi$.
Elliot Gorokhovsky
CC BY-SA 3.0
2015-09-08T18:14:34.740Z
Also, @HuckBennett, the paper I'm writing on this cites your master's thesis with Dr. Sankaranarayanan. The algorithm for counting the regexes is modified inclusion exclusion.
Elliot Gorokhovsky
CC BY-SA 3.0
2015-09-08T20:27:39.420Z
@HuckBennett I see my problem, the number of paths to accept state does not equal to number of accepting strings...
Chao Xu
CC BY-SA 3.0
2015-09-08T22:42:41.330Z
@RenéG: Wow! I'm glad that the exposition was useful to you, but in all honesty there might be better sources to look at.
Huck Bennett
CC BY-SA 3.0
2016-12-30T03:51:40.750Z
It's also interesting to look at the problem "Given an NFA, count the number of matching words of length $k$" when k is given in binary. This problem is PSPACE-hard. I say this based on the proof that deciding equivalence of two regular expressions is PSPACE-hard. In that reduction, one reg-ex was constructed to accept all strings, and the other to accept all strings that are not valid rejecting computation histories of PSPACE machine M on input w. Using that second regular expression and taking $k$ to be the length of a computation history of M on w makes this other problem PSPACE-hard too.
Mikhail Rudoy
<cc.complexity-theory><reference-request><complexity-classes>
Is counting the words in a finite regular language #P-complete?
Elliot Gorokhovsky
# Is counting the words in a finite regular language #P-complete?

(Asked by: username_0 on 2015-09-07)

Almost the exact same question was asked [here](https://cstheory.stackexchange.com/questions/8200/counting-words-accepted-by-a-regular-grammar), but nobody proved or cited its #P-completeness! I found this question because I proved it is #P-complete (proof below), and the proof was *trivial*, but I couldn't find it anywhere on the web or in the discussion on that question! (One person commented "I suspect it is #P-complete".) So either my proof is wrong, which you can judge for yourself, or the result is novel, which I would think is highly unlikely. Which is it?

---

**Proof:**

Consider the set of regular expressions formed by the union and concatenation of symbols from $(\Sigma\cup{.})$, where $\Sigma$ is an alphabet and $.$ is a symbol for any $l\in\Sigma$. I will show that #SAT reduces in $O(mn)$ time to counting the number of strings that satisfy such a regex, where $m$ is the number of clauses and $n$ is the number of variables in the given formula $\varphi$.

The reduction is very simple. First, reduce #SAT to #UNSAT by noting that if $\varphi$ has $n$ variables, then $\#\text{SAT}(\varphi) = 2^n - \#\text{UNSAT}(\varphi)$. So now we have to count the number of falsifying assignments of the variables of $\varphi$.

To falsify $\varphi$, it suffices to falsify just one clause. We therefore want to find
$$\left|\bigcup \limits\_{C\in\varphi}F(C)\right|$$
where $F(C)$ is the set of assignments of literals that falsify $C$.

We thus write a regex representing the language of falsifying assignments for each clause. Using $\Sigma = \{0,1\}$, and letting $r\_i$ be the $i^{th}$ symbol of a regex $r$, the regex for the language of assignments that falsify a clause $C$ is
$$
r\_i = \begin{cases}
0 & \text{if } x\_i\in C \\
1 & \text{if } \overline{x\_i}\in C \\
. & \text{otherwise}
\end{cases}
$$

We then take the union of the regexes for each clause $C\in\varphi$. For example, if $\varphi = (x\_1\vee \overline{x\_2}\vee x\_3) \wedge (x\_1\vee x\_3\vee \overline{x\_4})\wedge (\overline{x\_1}\vee \overline{x\_4})$ we would have $r = $`010.|0.01|1..1`, where `|` denotes union.

The construction yields a union of $m$ strings, each of $n$ symbols. Thus the reduction takes $O(mn)$ time and the size of the regex-counting instance is polynomial in the size of the formula. Further, any regular expression that uses only concatenation, dot, and union represents a finite regular language (specifically, there is no Kleene star). So since we can solve #SAT by counting strings that satisfy such a regex, we can say that counting the words in a finite language is #P-complete.

**Tags:** cc.complexity-theory, reference-request, complexity-classes
> **Comments:**
> **username_1**: "Almost the exact same question" they are very different. Your languages are finite.  
> **username_2**: @ChaoXu: but if it is #P-complete for finite languages, then  the problem "Given an NFA, count the number of matching words of length $k$" (the linked problem) is #P-complete when $k$ is given in unary ... so the two questions are not so different. However it seems a known result (see for example: http://dl.acm.org/citation.cfm?id=313803). Note that the problem is in P for *deterministic* finite automata.  
> **username_3**: @ChaoXu: How? I actually spent awhile thinking about this issue before Marzio's comment which is (I think) completely right.  
> **username_0**: @ChaoXu its equivalent, just take $n$ larger than the largest word in the language. In my problem $n$ is known as the number of variables of $\varphi$.  
> **username_0**: Also, @HuckBennett, the paper I'm writing on this cites your master's thesis with Dr. Sankaranarayanan. The algorithm for counting the regexes is modified inclusion exclusion.  
> **username_1**: @HuckBennett I see my problem, the number of paths to accept state does not equal to number of accepting strings...  
> **username_3**: @RenéG: Wow! I'm glad that the exposition was useful to you, but in all honesty there might be better sources to look at.  
> **username_4**: It's also interesting to look at the problem "Given an NFA, count the number of matching words of length $k$" when k is given in binary. This problem is PSPACE-hard. I say this based on the proof that deciding equivalence of two regular expressions is PSPACE-hard. In that reduction, one reg-ex was constructed to accept all strings, and the other to accept all strings that are not valid rejecting computation histories of PSPACE machine M on input w. Using that second regular expression and taking $k$ to be the length of a computation history of M on w makes this other problem PSPACE-hard too.  

---

## 1 answers

### Answer by username_5 on 2016-12-19. Score: 7

See this paper:
Counting the size of regular sequences of given length is #P-complete:
S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting
and random generation of strings in regular languages.
In ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 551–557, 1995.


---

