该语言的上下文无关语法

Question

我正在研究一些考试准备材料并陷入这个问题。

显示 L = {we {a,b}* 的上下文无关语法：w = wR 并且每个 a 后面紧跟着 ab}。

wR 是 w 的倒转。因此，在英语中，回文是每个“a”后跟一个“b”，使用任意数量的 a 和 b。

到目前为止，我得到了相反的部分，但我不知道如何合并每个 a 后面跟着 ab 部分，同时确保回文属性仍然成立。

S -> bSb | b | [the empty string]

非常感谢任何帮助！

Answer 1

由于每个“a”后面必须有一个“b”，并且得到的单词必须是回文（如果从末尾读到开头也是一样），这意味着每个“a”前面也必须有一个“b”。

我们从中间开始构建这个词，向两个方向发展。规则是，当中间部分以“a”（这是非终结符 A）结束（并因此开始）时，则其后面（和前面）必须是“b”。另一方面，当中间部分被“b”包围时（这是非终结符 B），它可以用单个“a”（前一种情况）或任意数量的“b”来扩展。中间偶数个“b”的特殊情况也得到处理。起始符号S只允许由“b”限制的单词，因此所有规则都匹配。

S -> B | [empty]
B -> bAb | bBb | bb | b
A -> aBa | a

编辑：我之前的解决方案不正确，我希望现在可以工作。