Complexity of counting words of given length in regular or context-free language 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.
 A: 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).
