Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines?

This can be done with an abvious brute-force search by listing all strings in lexicographic order and testing which belong to the language, but I would prefer some more tractable method.

share|improve this question
    
You mention brute-force, but what else is there for a total listing? Do you mean 'lazy' or do you mean an efficient 'next' operator (given a word in the language, give the next lexicographically)? Also, you can't mean 'all' if it is an infinite language, so do you mean all of a given length $n$? –  Mitch May 2 '11 at 14:08
    
@Mitch I mention "obvious brute-force" and "more tractable", where the obvious part is explained, thus I mean some more sensible method than the one going over all strings. And, yes, I mean an algorithm that will (eventually) list every word from the language. I also know that purists wouldn't call that algorithm in the first place as it does not stop (for infinite languages), but lets forget that for now. And, no, I'm not looking for way to print only words of a given length. Maybe up to some predefined length would go here (actually it could serve quite well - I need to think of this). –  rank May 2 '11 at 14:35
    
Oh...I overlooked your explanation of brute-force as essentially generate $\Sigma^{*}$ and test. Then dsg's answer sounds simplest, doing what the grammar says on sets of words (which you can restrict to length. That algorithm is conceptually the right thing, but depending on the size of the sets, can also be slow for small length (too much set manipulation), depending on the number of terminals. –  Mitch May 2 '11 at 14:55

1 Answer 1

up vote 2 down vote accepted

Yes, this can be done using a recursive algorithm called expand as follows.

expand will take in a node in the grammar and return a set of trees that can be generated from that node.

In the base case, expand is given a terminal and returns a singleton set containing a leaf (one node tree) for that terminal.

In the recursive case, expand is given a node, say $X$, that can be rewritten as $Y_1 Y_2 \ldots Y_n$ via CFG rule $X \to Y_1 Y_2 \ldots Y_n$. expand combines the trees, $z_i$, returned from the recursive calls on each of the $Y_i$ using a Cartesian product. That is, expand(X) will return the following set of trees: $\left\{ X \to z_1 z_2 \ldots z_n \mid z_i \in \text{expand}(Y_i) \right\}$. Here, each tree in the set is rooted at $X$ and contains the trees from the recursive calls as its children.

EDIT

For efficiency, you can use a different collection instead of sets (e.g. array / list). As long as there is no spurious ambiguity, you will compute the same answer. If the grammar turns out to be infinite, replace the sets in the algorithm with lazy streams, and it will continue to work.

share|improve this answer
    
I will think this over hopefully today. I came up with an idea which seems close to your suggestion, but the problems in the implementation seem to be more technical than "logical". I'll try this out with Haskell and see if it comes out as I thought. –  rank May 3 '11 at 3:26
    
@rank -- It's easier to implement for CFGs in Chomsky Normal Form (production rules of arity $\leq 2$) because the Cartesian product is no harder than a simple list comprehension (cartProd xs ys = [(x,y) | x <- xs, y <- ys]). StackOverflow has some nice pointers for larger products. –  dsg May 3 '11 at 3:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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