2

是否有一种算法可以从给定的上下文无关语法生成所有字符串？

4

2 回答 2

7

莱昂纳多的回答在技术上是正确的；没有终止算法可以返回一般 CFG 的单词集，因为该集通常是无限的。

但是有些算法会为 CFG生成一个单词序列，每个匹配语法的单词都会“最终”出现。其中之一应该足以满足您的目的。yield用Python 之类的语言编写其中的一个是相当容易的。

这种算法的草图（恐怕是相当绝望的伪代码）：

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)

假设语法已被转换，使得每个构造为零到两个终结符，这将在语法的所有解析树的树上运行广度优先搜索。BFS 是必要的，因为任何给定子树的大小都可能是无限的——DFS 可能会一直卡在向下看其中之一。

等待给定的任何解析树实现的时间和内存成本可能是任意的，但对于该解析树来说是有限的。

于 2010-11-22T11:11:16.663 回答
3

问：有没有一种算法可以从给定的上下文无关文法生成所有字符串？

答：不，语法是一组定义单词的规则，某些语法会生成一定数量的单词，但是绝大多数会生成无穷多的单词，所以不，没有算法可以从给定的语法生成所有字符串

于 2010-11-22T10:36:54.077 回答