首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >需要上下文无关语法,其中一个字符的数量是另一个字符的5倍。

需要上下文无关语法,其中一个字符的数量是另一个字符的5倍。
EN

Stack Overflow用户
提问于 2012-03-21 18:39:47
回答 1查看 1.3K关注 0票数 2

我很肯定我确实有一个,但它有42个建筑规则,并不是很好的概括。我怎样才能用更少的建筑规则来做呢?

语言是{a,b}*,其中a的数目是b的5倍。

我知道,对于语言{a^n (串联) b^m;m= 5n},它只是

S= aSbbbbb =λ

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

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2012-03-21 18:58:07

首先,请注意,如果一个句子的字符数是另一个的5倍,那么它总是类似于aaabaabaaaaa。所以一个句子可以是aaaaabaaabaa。另一个观察是,每当我们添加一个b时,我们必须添加五个a字符。

实际上,以下语法中的a字符是b字符的五倍:

代码语言:javascript
复制
S = AS | λ
A = Baaaaa | aBaaaa | aaBaaa | aaaBaa | aaaaBa | aaaaaB
B = bS | Sb

我们从S开始,它可以通过空(满足需求)或A

A规则至少生成5个a字符和一个B。现在,对于B,我们可以放置b并在那里停止(选择S的空字符串)或重新开始(选择SA )。这保证了我们总是放置5倍于a字符的b字符。

最后,这种语法可以很容易地推广到语法中,而不需要包含一个字符和另一个字符的n次数(通过直接扩展规则A)。

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/9810822

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档