为给定语言创建上下文无关语法
我得到了语言
{b a^m1 ba^m2 ba^m3 .... ba^mn | n >= 2, m1,...,mn >= 0, and mi != mj for some i.j}
，也就是说，它以 ab 开头，至少有 2 个 b，并且它们之间有不同数量的 a。例如，“bab”，“bba”，“bbba”，“babbab”，...但不是“bb”，“baba”，“babaaba”，...
我如何为这种语言创建CFG。
我已经有了以下内容，但我似乎无法完成超过 2 个 b；我也不太确定我的一般方法是否正确。
S -> bAbaA | baAbA.
A -> aaA | ε.
I am given the language
{b a^m1 ba^m2 ba^m3 .... ba^mn | n >= 2, m1,...,mn >= 0, and mi != mj for some i.j}
That is, it strings with beginning with a b and at least 2 b's and somewhere a different number of a's between them. E.g., "bab", "bba", "bbba", "babbab",... but not "bb", "baba", "babaaba",...
How can I create a CFG for this language.
I already have something the following but I can't seem to make it complete it for more than 2 b's; I'm also not so sure if my general approach is correct.
S -> bAbaA | baAbA.
A -> aaA | ε.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
要做的第一件事是应用 CFG 的泵送引理并确保它是一个 CFG。乍一看似乎并非如此。
The first thing to do is apply the pumping lemma for CFGs and make sure that is a CFG. First glance looks like it may not be.