2
$\begingroup$

Given a CFG for a (infinite) language $L$, is there an efficient algorithm that generates all possible words of length $n$ in $L$?

Preferably efficient in time, and with low memory usage.

I'm only interested in the words themselves - not their derivations. If the language is ambiguous and has multiple derivations for a word it would be nice if there is an efficient way to make sure each word is only output once.

The order of the words is irrelevant. If time can be saved by preprocessing the grammar $G$ (e.g. to CNF) then that's perfectly fine.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

I can suggest one possible algorithm based on memoization of a rather naive recursive algorithm, with some corner cases cleaned up. I don't know if there might be a better approach.

Convert the grammar to Chomsky normal form. Let $L(A,\ell)$ denote the set of words of length $\ell$ in $L(A)$ (i.e., all words of length $\ell$ that can be derived from $A$). We'll construct an algorithm to compute $L(S,n)$ recursively, where $S$ is the start symbol of the grammar.

The recursive algorithm for computing $L(A,\ell)$ works as follows. If we have a rule $A \to \varepsilon$ and $\ell=0$, add $\varepsilon$ to the output; for each rule $A \to a$, if $\ell=1$, add $a$ to the output; for each rule $A \to BC$ and each $0 \le i \le \ell$, add $uv$ to the output for each $u \in L(B,i)$ and $v \in L(C,\ell-i)$.

Memoize this algorithm.

As an optimization, when considering a rule $A \to BC$, only iterate over $i$ such that $0 \le i \le \ell$ and $L(B,i)$ is non-empty and $L(C,\ell-i)$ is non-empty. This prevents generating a long list of candidate values for $u$ that you'll never use. (You can precompute whether $L(A,i)$ is empty or not, for each symbol $A$ and each $0 \le i \le n$, in $O(n^2 |G|)$ time using dynamic programming, where $|G|$ is the number of rules in the grammar.) Or equivalently, when you implement the recursive algorithm, implement it using lazy lists, so that the output of $L(A,\ell)$ is a lazy list with elements generated on demand.

With this optimization, I think the total running time of this algorithm should now become something like $O(m n^2 |G|)$, where $m$ is the total number of words of length $n$ in $L$ and $|G|$ is the number of rules in the grammar. Maybe there is a tighter bound on the running time: this might be pessimistic.

$\endgroup$
11
  • $\begingroup$ Hrm, what is the memory complexity? And does it output ambiguous words multiple times? I'd really prefer polynomial memory usage in terms of $|G|$ if possible. My idea was something akin to converting to Greinbach normal form, maintaining a stack of $LR(0)$ item sets, where we build the words by viable prefixes in lexicographic order. $\endgroup$
    – orlp
    Apr 16, 2018 at 22:40
  • $\begingroup$ When I say $LR(0)$ item sets I actually meant more like Earley item sets, where each $LR(0)$ item is augmented with an originating item set index. In fact I just realized the algorithm I described is essentially an Earley parser that instead of scanning at every step it iterates over all possible terminals it could scan at that position, and recursively continuing from those (backtracking afterwards). $\endgroup$
    – orlp
    Apr 16, 2018 at 22:55
  • $\begingroup$ Actually, using Greinbach normal form, wouldn't it be possibly quite efficient to work backwards, and meet in the middle? For example we know that the last character must be a nonterminal with rule $A \rightarrow a$, where (if $\ell > 1$) furthermore $A$ must be present in a rule $B \rightarrow b \alpha A$, which would also give you a set of possible first characters. Then you can recursively continue generating all words of size $\ell - 2$ with start symbol $S \rightarrow \alpha$. $\endgroup$
    – orlp
    Apr 16, 2018 at 23:07
  • $\begingroup$ This looks interesting: sis.uta.fi/cs/reports/pdf/A-1997-4.pdf. In the meantime, I programmed my approach, which works (albeit not as fast as I'd like): gist.github.com/orlp/ba8594a613ad3d98441b3ff29e916342 EDIT: never mind on that paper, it only gives an efficient solution for regular languages and prefix-free cfgs. $\endgroup$
    – orlp
    Apr 17, 2018 at 1:01
  • $\begingroup$ @orlp, In my scheme, memory complexity should be at most $O(mnt)$ where $t$ is the number of nonterminals (which might not be very useful, I realize). You can avoid duplicates by hashing. I don't know if there's a better way that further reduces memory consumption. Your working backwards idea doesn't seem to take into account that some nonterminals can derive $\varepsilon$, e.g., the last character might come from a nonterminal with rule $A \to aB$ where $B \to \varepsilon$. $\endgroup$
    – D.W.
    Apr 17, 2018 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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