context-free-grammar - 是 { w | w <> w^R } 在字母表 {0,1} 上是一种上下文无关的语言？

Question

我真的很想帮助您决定字母表中所有单词的语言是否{0,1}不能从两边以同样的方式读取，{ w | w <> wR } , 是一种上下文无关语言(即可以转化为特定的语法规则)。

我试图通过抽水引理证明它不是上下文无关语言，但我没有找到会导致我矛盾的字符串。

有什么建议么？

Answer 1

如果我正确阅读了您的问题，那么您正在寻找非回文集是否是上下文无关语言。

它是一种上下文无关语言:

S --> 0S0 | 1S1 | R
R --> 0V1 | 1V0
V --> 0V0 | 1V1 | R | 1 | 0 | ε

从 S 开始，概念是从外向内构建字符串。 S 允许您根据需要放置尽可能多的匹配 1 或 0(可能没有)，直到遇到 R 的情况，其中存在不匹配。从那时起，您可以放置​​匹配或非匹配(因为此时我们已经保证不是回文。)这足以描述所有非回文——从外到内，它们以零或更多匹配对，然后是一对不匹配对，然后是零对或多对(匹配或不匹配)。最后，中间可能有也可能没有字符。

附言如果你还没有，Sipser 的《计算理论》这本书无疑是非常好的。事实上，这是唯一一本我仍然不时阅读的大学书籍。