context-free-grammar - 非回文的上下文无关语法

Question

所以我发现一个人在这里询问非回文的 上下文无关语法：非回文的上下文无关语法

给定的 CFG 是：

R -> XRX | S
S -> aTb | bTa
T -> XTX | X | <epsilon>
X -> a | b

和

R -> aRa | bRb | S
S -> aTb | bTa
T -> aTa | bTb | a | b | <epsilon>

我的问题：尽管它不是回文，但这个 CFG 不会不接受 'aaabba' 吗？如果这个 CFG 的规则更像：

T -> aTa | bTb | aTb | bTa | a | b | <epsilon>

而不是上面给出的最后一行？还是我误解了什么？:<

Answer 1

第一个很好，但第二个不是。

对于第一个，顺序是

R -> XRX -> aRa -> aSa -> aaTba -> aaXTXba -> aaaTbba -> aaabba.

我相信您说第二个无法生成所有非回文是正确的。