This is #P hard via counting solution to monotone DNF formula.

Let $\phi(x_1,...x_n)$ be monotone DNF formula on $n$ variables.

We are trying to find regular language $L$ over alphabet $\{0,1\}$
with all words of length $n$ and the words in $L$ are in one
to one correspondence with the satisfying assignment of $\phi$.

Variable $x_i$ in $\phi$ corresponds to $i$-th element in a word
$\{0,1\}^n$.

To satisfy clause $c^j$ in $\phi$, we match the indexes of the variables
in $c^j$ in a regular expression $W$ and the rest of the variables can be
arbitrary.

More formally set the regular expression
$W^j[i]=1$ if $x_i \in c^j$,
otherwise, set $W^j[i]=0 + 1$ where $+$ denotes union. (If necessary we can allow negative literal $\lnot x_i$ by setting $W^j[i]=0$

E.g. for the clause $(x_1 \land x_4)$ we set $W^1=1 \; 0+1 \; 0+1 \; 1$.

Finally, set $L = W^1 + W^2+ \cdots+ W^m$.

So far, $L$ is defined by regex. Experimentally it appears
to have NFA with polynomial size in $n$ (the grammar is obviously small).

5more comments