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$ Apr 2, 2014 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$ Apr 2, 2014 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$ Apr 2, 2014 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$ Apr 2, 2014 at 13:53
  • 2
    $\begingroup$ It's #P complete $\endgroup$ Sep 7, 2015 at 19:26

1 Answer 1

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.