Context free grammars

Question

Is there an algorithm that generates all strings from a given context-free grammar?

Answer 1

Leonardo's answer is technically correct; there's no terminating algorithm that will return the set of words for a general CFG, because oftentimes that set is infinite.

But there are algorithms that will generate a sequence of words for a CFG, with every word matching the grammar appearing "eventually". One of these should be enough for your purposes. It is fairly easy to write one of these in a language with yield, such as Python.

A sketch of such an algorithm (in rather hopeless pseudocode, I'm afraid):

generate(g):
    if g is empty:
        yield ""
    otherwise if g is a terminal a:
        yield "a"
    otherwise if g is a single nonterminal:
        for c in every construction of g:
            start a generator for generate(c)
        until all generators are exhausted:
            looping over each nonexhausted generator gen:
                yield "a" where a = next(gen)
    otherwise if g is a pair of symbols m and n:
        for c in every construction of m:
            start a generator in set 1 for generate(c)
        for d in every construction of m:
            start a generator in set 2 for generate(d)
        until all in set 1 or all in set 2 are exhausted:
            loop over all pairs gen1,gen2 of nonexhausted in set 1 and set 2:
                yield "a b" where a = next(gen1) and b = next(gen2)

Assuming the grammar has been converted so that each construction is zero to two terminals, this will run a breadth first search over the tree of all parse trees of the grammar. BFS is necessary, because the size of any given subtree may be infinite -- a DFS could be stuck looking down one of them forever.

The time and memory cost of waiting for given any parse tree to materialise may be arbitrary, but it is finite for that parse tree.

Answer 2

Q:Is there an algorithm that generates all strings from a given context-free grammar?

A: No, a grammar is a set of rules to define words, certain grammars generate a certain number of words, but the vast mojority generate a infinty words, so no, theres no algo that generates all strings from a given grammar