我正在研究一些测试准备材料并坚持这个问题 .
Show a context free grammar for L = {w e {a,b}*: w = wR and every a is immediately followed by a b}.
wR反过来了 . 因此，在英语中，一个回文，每个“a”后跟一个“b”，使用任意数量的a和b .
到目前为止，我得到了相反的部分，但我无法弄清楚如何合并每个a后跟一个b部分，同时确保回文属性仍将保持 .
S -> bSb | b | [the empty string]
任何帮助是极大的赞赏！
1 回答
因为每个“a”后面必须跟一个“b”，所得到的单词必须是回文（如果从末尾到开头读取它是相同的），这意味着每个“a”也必须先于a “b” .
我们从中间开始构建单词，向两个方向发展 . 规则是当中间部分以“a”（这是非终结符号A）结束（并因此开始）时，必须遵循（并且先于）“b” . 另一方面，当中间部分被“b”（这是非终结符号B）所包围时，它可以用单个“a”（前一个例子）或任何数量的“b”扩展 . 在中间均匀编号为“b”的特殊情况也被处理 . 起始符号S仅允许由“b”限制的单词，因此所有规则都匹配 .
编辑：我以前的解决方案不正确，我希望现在可以使用 .