context-free-grammar - 如何编写上下文无关语法？

Question

我正在尝试在字母表Σ = {a,b}上为所有以相同数量的 's 开头和结尾的单词写一个 CFG，中间a至少有一个b。

现在我了解了 CFG、变量、生产规则等的基本概念。不幸的是，我已经没有编写上述 CFG 的想法了。到目前为止我所拥有的是

S → aYXYa
X → XbX | b | λ
Y → ???

我认为生产规则会给我一个字符串，两边都有两个 ** S** ，中间有尽可能多的 ** **。但是，我不确定如何在 ** ** 的两侧放置尽可能多的** **，同时确保每侧的 ** ** 数量完全相同。Xababa

任何建议，解决方案将不胜感激。谢谢。

score 7 · Accepted Answer

作为以前教过这门课的前教授，我不会给你答案。不过，我会给你一个提示：

你有正确的想法将它分成两部分，a 和其余部分。但是，您没有做对其中任何一个。

首先尝试写作： an ⁿ ba ⁿ 然后从那里分支。

希望有帮助。

score 3 · Accepted Answer

S → aSa | 乙
乙→乙| bB

这应该是您要查找的 CFG。每当您在开始和结束时处理相同的事情时，请记住您不能保证相同的 var 将以相同的方式填充。因此，您必须明确说明。

score 1 · Accepted Answer

自从我的 CS 本科生以来已经有一段时间了，但这看起来很合理：

S -> aSa | bX

X -> bX | 乙

Basically, you start with S and add as many pairs of a's as you want and then switch to X and add as many b's as you want.

3 回答 3