regex - 如何使用正则表达式检查字符串是否为回文？

Question

这是一个我无法回答的面试问题:

如何使用正则表达式检查字符串是否为回文？

附:已经有一个问题“How to check if the given string is palindrome?”，它给出了很多不同语言的答案，但没有使用正则表达式的答案。

Answer 1

这个问题的答案是“不可能”。更具体地说，面试官想知道你是否在计算理论课上集中注意力。

在计算理论课上，您学习了有限状态机。有限状态机由节点和边组成。每条边都用有限字母表中的一个字母进行注释。一个或多个节点是特殊的“接受”节点，一个节点是“起始”节点。当从给定单词中读取每个字母时，我们会遍历机器中的给定边缘。如果我们最终处于接受状态，那么我们就说机器“接受”该词。

正则表达式始终可以转换为等效的有限状态机。也就是说，接受和拒绝与正则表达式相同的单词(在现实世界中，某些正则表达式语言允许任意函数，这些函数不算在内)。

不可能构建一个接受所有回文的有限状态机。证明依赖于这样的事实:我们可以轻松构建一个需要任意大量节点的字符串，即字符串

a^x b a^x(例如，aba、aabaa、aaabaaa、aaaabaaaa、...)

其中 a^x 是 a 重复 x 次。这至少需要 x 个节点，因为在看到“b”之后，我们必须倒数 x 次以确保它是回文。

最后，回到最初的问题，你可以告诉面试官你可以编写一个正则表达式来接受所有小于某个有限固定长度的回文。如果现实世界中有一个应用程序需要识别回文，那么它几乎肯定不会包含任意长的回文，因此这个答案将表明您可以区分理论上的不可能与现实世界的应用程序。尽管如此，实际的正则表达式仍然相当长，比等效的 4 行程序长得多(对读者来说很容易练习:编写一个识别回文的程序)。