Is counting the words in a finite regular language #P-complete? Almost the exact same question was asked here, 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 &amp; \text{if } x_i\in C \\
         1 &amp; \text{if } \overline{x_i}\in C \\
         . &amp; \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.
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.