是{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允许你为你想要的(可能没有),直到你达到R的情况下,其中有一个不匹配的地方尽可能多的匹配1或0.从那里你可以放置匹配或不匹配(因为此时我们已经保证不是回文.)这足以描述所有非回文 - 从外到内,它们从零开始或者更多匹配对,然后是一个不匹配对,然后是零个或多个对(匹配与否).最后,中间可能有也可能没有角色.

PS如果你还没有它,那么Sipser关于计算理论的书无疑是优秀的.事实上,这是我不时阅读的唯一一本大学书.