13

我真的很喜欢你的帮助来决定字母表上所有单词的语言是否{0,1}不能以相同的方式从两边读取，是否是一种上下文无关的语言（也就是说，它可以转换为特定的语法规则）。{ w | w <> wR }

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

有什么建议么？

4

2 回答 2

12

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

它是一种上下文无关的语言：

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

从 S 开始，概念是从外向内构建字符串。 S 允许您放置任意数量的匹配 1 或 0（可能没有），直到遇到不匹配的 R 情况。从那里你可以放置匹配或非匹配（因为此时我们已经保证不是回文。）这足以描述所有非回文 - 从外到内，它们从零开始或更多匹配对，然后是一对不匹配对，然后是零个或更多对（匹配或不匹配）。最后，中间可能有也可能没有字符。

PS 如果你还没有，Sipser 的计算理论书无疑是优秀的。事实上，这是我时不时读的唯一一本大学书。

于 2012-04-05T16:51:39.187 回答
2

诚然，作为一名计算机科学家，这个问题超出了我的想象。但是，作为一名数学家，我在这里有一些贡献。

如果w它本身是一种上下文无关语言，则存在一个闭包来解决 的反转w：

上下文无关语言在以下操作下关闭。也就是说，如果L和P是上下文无关语言，则以下语言也是上下文无关的：

...

  • L的反转

这似乎就是这里被问到的全部内容。这些参考资料提供了有关如何导出初始和后续封闭形式的额外背景信息。

（额外的，来自集合论的潜在有用参考）

于 2012-04-04T22:38:41.390 回答