我真的很乐意帮助你决定是否所有单词的语言 {0,1} 无法以相同的方式从双方读取， { w | w <> wR } 是一种无上下文的语言（也就是说，它可以转化为具体的语法规则） .
{0,1}
{ w | w <> wR }
我试图通过泵浦引理证明它不是一种无上下文的语言，但是我找不到会导致我矛盾的字符串 .
有什么建议？
如果我正确地阅读了你的问题，那么你正在寻找一组非回文是否是一种无语境的语言 .
它是一种无上下文的语言：
S --> 0S0 | 1S1 | R R --> 0V1 | 1V0 V --> 0V0 | 1V1 | R | 1 | 0 | ε
从S开始，概念是从外部构建字符串.S允许您根据需要放置尽可能多的匹配的1或零（可能没有），直到达到R不匹配的情况为止 . 从那里你可以放置匹配或不匹配（因为此时我们已经保证不是回文 . ）这足以描述所有非回文 - 从外到内，它们从零开始或者更多匹配对，然后是一个不匹配对，然后是零个或多个对（匹配与否） . 最后，中间可能有也可能没有角色 .
附：如果你还没有它，那么Sipser关于计算理论的书无疑是非常好的 . 事实上，这是我不时阅读的唯一一本大学书 .
作为一名计算机科学家，这个问题无疑是我的头脑 . 但是，作为一名数学家，我在这里有所贡献 .
如果 w 本身是一种无上下文的语言，a closure exists to solve the reversal of w：
w
在以下操作下关闭无上下文语言 . 也就是说，如果L和P是无上下文的语言，则以下语言也是无上下文的：...... L的逆转
这似乎就是这里所要求的 . These references提供有关如何派生初始和后续封闭表格的其他背景信息 .
（Additional, potentially helpful reference from set theory）
2 回答
如果我正确地阅读了你的问题，那么你正在寻找一组非回文是否是一种无语境的语言 .
它是一种无上下文的语言：
从S开始，概念是从外部构建字符串.S允许您根据需要放置尽可能多的匹配的1或零（可能没有），直到达到R不匹配的情况为止 . 从那里你可以放置匹配或不匹配（因为此时我们已经保证不是回文 . ）这足以描述所有非回文 - 从外到内，它们从零开始或者更多匹配对，然后是一个不匹配对，然后是零个或多个对（匹配与否） . 最后，中间可能有也可能没有角色 .
附：如果你还没有它，那么Sipser关于计算理论的书无疑是非常好的 . 事实上，这是我不时阅读的唯一一本大学书 .
作为一名计算机科学家，这个问题无疑是我的头脑 . 但是，作为一名数学家，我在这里有所贡献 .
如果
w本身是一种无上下文的语言，a closure exists to solve the reversal of w：这似乎就是这里所要求的 . These references提供有关如何派生初始和后续封闭表格的其他背景信息 .
（Additional, potentially helpful reference from set theory）