Let $L$ be a regular or context-free language over alphabet $\{0,1\}$.
What is the complexity of counting words of length $n$ in $L$?
Is it possible to efficiently find if for given $n$ all words of length $n$ are in $L$?
If one can construct DFA for regular language I believe it is equivalent to counting paths in graph, but constructing DFA might not be tractable I suppose.
$L$ might be ambiguous.
Added
The language is given as grammar and assume constructing DFA is intractable.
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).
