4

问题是实现一种算法，该算法从给定的上下文无关语法G生成长度在l和r之间的所有字符串。

我想出了简单的方法：在语法图上运行 BFS，记住状态。但它在一些递归规则上失败了：

(1)   S -> 0 | SSS | λ

我不能简单地限制最大字符串长度，因为规则可以包含 λ（空字符串），所以非终结符可以减少最终字符串长度。（例如，使用 运行 (1) l = 1， r = 2在我的实现中将仅输出 0）

我也尝试限制应用规则的最大数量，但这显然也是错误的。

我如何限制或更改我的算法，使其永远不会陷入无限循环并正常工作？

4

1 回答 1

3

您可以将语法转换为Greibach 范式，然后创建中的每一步1都会 增加生成的单词的大小，并且您将能够限制单词的长度，如问题中最初解释的那样。

(1) 如果空词在语法中，可能除了第一个

于 2012-09-20T15:19:59.357 回答