我很确定我确实有一个，但它有 42 条构造规则并且不能很好地概括。我怎样才能用更少的构建规则来做到这一点？
语言为 {a,b}*，其中 a 的数量是 b 数量的五倍。
我知道对于一种语言 {a^n (连接) b^m; m = 5n} 就这样
S = aSbbbbb | λ
但是当字符可以按任何顺序排列时，我就迷路了。
最佳答案
首先，观察一下，如果一个句子的字符数是另一个句子的 5 倍，它总是看起来像 aaabaabaaaaa。因此一个句子可以是 aaaaab 或 aaabaa。另一个观察结果是，每当我们添加 b 时，我们都必须添加五个 a 字符。
以下语法的 a 字符数量确实是 b 字符数量的五倍:
S = AS | λ
A = Baaaaa | aBaaaa | aaBaaa | aaaBaa | aaaaBa | aaaaaB
B = bS | Sb
我们从S开始，它可以是空(满足要求)或A。
A 的规则生成至少 5 个 a 字符和一个 B。现在对于 B，我们可以放置 b 并在那里停止(通过为 S 选择空字符串)或重新开始(通过选择 A代表S)。这保证了我们放置的 a 字符数始终是 b 字符数的 5 倍。
最后，这种语法可以很容易地推广到一种语法，它需要包含一个语法的 n 倍于另一个语法的字符(通过直接扩展规则 A)。
关于context-free-grammar - 需要一种上下文无关语法，其中一个字符的数量是另一个字符的 5 倍，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9810822/