问题是实现一个算法，该算法根据给定的上下文无关语法 G 生成长度在 l 和 r 之间的所有字符串。
我想出了一个简单的方法:在语法图上运行 BFS，记住状态。 但它在某些递归规则上失败了:
(1) S -> 0 | SSS | λ
我不能简单地限制最大字符串长度，因为规则可以包含 λ(空字符串)，因此非终结符可以减少最终字符串长度。 (例如，使用 l = 1 运行 (1)，r = 2 在我的实现中将只输出 0)
我也试过限制应用规则的最大数量，但显然也是错误的。
我如何限制或更改我的算法，使其永远不会陷入无限循环并正常工作？
最佳答案
您可以将语法转换为 Greibach normal form ，然后创建过程中的每个步骤1 都会增加所生成单词的大小，您将能够按照问题中最初解释的那样限制单词的长度。
(1) 除了可能的第一个，如果空词在语法中
关于algorithm - 从上下文无关文法生成字符串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12515369/