context-free-grammar - 此语言的上下文无关语法

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”之前也必须有一个“乙”。

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

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

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