6
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ take a look:cstheory.stackexchange.com/questions/8200/… $\endgroup$ – Fayez Abdlrazaq Deab Apr 2 '14 at 10:37
  • 2
    $\begingroup$ If the grammar is context free and unambiguous the Chomsky-Schutzenberger method give a system of algebraic equations. The ambiguous case is more complicated. If the language is left regular an unambiguous you get a linear system. $\endgroup$ – Benjamin Steinberg Apr 2 '14 at 13:22
  • 1
    $\begingroup$ A language is inherently ambiguous iff all its grammars are ambiguous. There are cfl's like that. But regular languages are never inherently ambiguous so you mean to say the grammar is ambiguous. This gets tricky. $\endgroup$ – Benjamin Steinberg Apr 2 '14 at 13:40
  • 1
    $\begingroup$ cseweb.ucsd.edu/~maackerman/… seems to give a polytime algorithm to enumerate lexicographically all words of length n accepted by an nfa. $\endgroup$ – Benjamin Steinberg Apr 2 '14 at 13:53
  • 2
    $\begingroup$ It's #P complete $\endgroup$ – Elliot Gorokhovsky Sep 7 '15 at 19:26
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.