今天看到一个有趣的正则表达式，是用来判断一个数是否为质数。说到这儿肯定有人犯迷糊了，正则是用来匹配字符串的呀，怎么可以用来验证数字呢? 别急嘛，首先我们得做一个转换，把数字转换成字符。假定需要验证的数字是N，转换的基本字符为1，那么转换出来的字符串就是N个1。这个用Python是挺容易实现的，只需要'1'*N就可以了。
嗯，确定了输入，现在是Magic时间，对于经过这样处理过的数字，我们只需要使用
^1?$|^(11+)\1+$
这个正则表达式进行匹配，如果能够匹配，则该数为合数，否则，该数为质数。
好吧，让我们先来验证一下，使用如下的Python脚本输出100以内的质数:
import re r = re.compile(r'^1?$|^(11+)\1+$') for i in xrange(100): if not r.match('1' * i): print i,
以下是运行结果:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
嗯，好像挺准的。可是为啥呢? 让我们来好好分析一下这个正则表达式。红字的那部分，挺简单的，匹配空字符和单个1，对应的数字是0和1，这样就排除掉这两个特殊的家伙(好像我记得前几年为1平反了，现在这玩意儿是质数了?)。再来看蓝色的部分，这部分首先出现的是^(11+)，这是匹配多于2个1的连续字符，这儿用括号进行了分组，为后面的\1提供内容，而后面的\1+$则是要求余下的字符串正好能被至少一个刚刚匹配的n个连续的1分区覆盖，具体地说，正则处理器首先尝试能否首先匹配2个1，然后看余下的字符数是否是2的倍数，如果不是，尝试首先匹配3个1，然后看余下的字符数是否是3的倍数，以此类推，这是不是和我们平时判断一个数是否是质数的方法一致呢? :)
这个式子最奇妙的还是在于\1，这个是判断的核心，我对正则的理解还停留在学习计算理论那会儿，分组结果能在匹配结束前使用倒还是第一次见到，于是翻了Python的文档才发现我已经out了……计算理论里说正则和DFA是等价的，于是就想试试把这个正则画成DFA，结果，掩面，我愧对Rudolf啊，学的全忘了，只能画出来一个无限状态机 OTL
题外话，找不到画图的东西，就用Keynote凑活了，结果没想到还不错……
话说如果有哪位童鞋能画个与这个正则匹配的DFA出来，请不吝赐教，拜 orz~
你画的这是啥啥啥啥啥啥啥啥
展开回复(1)
相当不简练的状态机而已……