context-free-grammar - 需要一个无上下文语法，其中一个字符的数量是另一个字符的 5 倍

Question

我很确定我确实有一个，但它有 42 条构造规则并且不能很好地概括。我怎样才能用更少的构造规则来做到这一点？

语言是 {a,b}*，其中 a 的数量是 b 的数量的五倍。

我知道对于一种语言 {a^n (concatenate) b^m; m = 5n} 它只是

S = aSbbbbb | λ

但是当角色可以按任何顺序排列时，我就迷路了。

Answer 1

首先，观察如果一个句子的字符数是另一个句子的 5 倍，它总是看起来像aaabaabaaaaa. 所以一个句子可以是aaaaabor aaabaa。另一个观察是，每当我们添加 a 时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）或重新开始（通过选择Afor S）。这保证了我们总是放置 5 倍于a字符的b字符。

最后，这种文法可以很容易地推广到一种文法，它需要包含一个比n另一个多倍的字符（通过直接扩展 rule A）。