python正则表达式判断字符串是否为回⽂_如何使⽤正则表达
式检查字符串是回⽂？...
这个问题的答案是“这是不可能的”。更具体地说，⾯试官想知道你是否在计算理论课上引起了注意。
在您的计算理论课中，您学习了有限状态机。有限状态机由节点和边组成。每个边都⽤有限字母表中的字母注释。⼀个或多个节点是特殊的“接受”节点，⼀个节点是“开始”节点。当从给定的单词中读取每个字母时，我们遍历机器中的给定边缘。如果我们最终处于接受状态，那么我们就说机器“接受”了这个词。
正则表达式总是可以转换为等效的有限状态机。也就是说，接受和拒绝与正则表达式相同的单词(在现实世界中，⼀些正则表达式语⾔允许任意函数，这些不计算)。
建⽴⼀个接受所有回⽂的有限状态机是不可能的。证据依赖于我们可以轻松构建⼀个需要任意⼤量节点的字符串的事实，即字符串
python正则表达式不包含a ^ xba ^ x(例如，aba，aabaa，aaabaaa，aaaabaaaa，....)
其中a ^ x是重复的x次。这需要⾄少x个节点，因为在看到'b'之后我们必须重新计算x次以确保它是回⽂。
最后，回到最初的问题，你可以告诉采访者你可以编写⼀个正则表达式，接受所有⼩于某个有限固定长度的回⽂。如果有⼀个真实世界的应⽤需要识别回⽂，那么它⼏乎肯定不会包含任意长的回答，因此这个答案将表明你可以将理论上的不可能性与现实世界的应⽤区分开来。实际的正则表达式相当长，⽐同等的4⾏程序长得多(读者容易练习：写⼀个识别回⽂的程序)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。