我很肯定我确实有一个,但它有42个建筑规则,并不是很好的概括。我怎样才能用更少的建筑规则来做呢?
语言是{a,b}*,其中a的数目是b的5倍。
我知道,对于语言{a^n (串联) b^m;m= 5n},它只是
S= aSbbbbb =λ
但当角色可以按任何顺序排列时,我就迷路了。
发布于 2012-03-21 18:58:07
首先,请注意,如果一个句子的字符数是另一个的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的空字符串)或重新开始(选择S的A )。这保证了我们总是放置5倍于a字符的b字符。
最后,这种语法可以很容易地推广到语法中,而不需要包含一个字符和另一个字符的n次数(通过直接扩展规则A)。
https://stackoverflow.com/questions/9810822
复制相似问题