子午门的夜巡队
一、一道令，两支队伍
子午门是皇城的一道门，入夜要查"腰牌"——只有腰牌上刻着规定字样的行人，才准放行。
往年查腰牌，规矩简单：腰牌上刻"内"字的放行，刻别的字，一律拦下。守门的兵丁一伸手就验得出来。
可今年，宫里换了新规矩，腰牌上的字样复杂起来。
新规矩是这么定的：腰牌上必须刻着"甲"、"乙"、"丙"三个字中的任意一个开头，然后后面可以跟"丁"或"戊"，再往后，"己"字出现至少一次……老太监念了一长串，末了补一句："总之，合乎这套规矩的腰牌，才准放行。"
守门的秦把总听得直挠头："这怎么验？腰牌上的字刻得歪歪扭扭，每块还不一样长。"
老太监冷笑一声，丢给他一张纸："这是令。能不能守好这道门，看你的本事了。"
秦把总打开纸——纸上画着一副图：一堆圆圈，圈里写着甲乙丙丁戊己，圆圈之间画着箭头，箭头边上标着"见某字走哪条路"。有的圆圈，一瞧见某个字，能同时往两条路走。
"这画的什么？"秦把总问手下的夜巡队。
"回把总，"一个识字的兵说，"这像是'验牌的章程'——从第一个圈开始，见一个字走一条箭头；走到头要是落在'打勾'的圈里，这块腰牌就算合格。"
"那这'同时走两条路'的圈，是怎么回事？"
"这……小的也不明白。"
二、一支队伍，变成"两条腿"
老太监画的图，秦把总看了半宿，看明白了大半——可那"一分为二"的圈，实在让他犯难。
他把夜巡队的队长老周找来。老周守了二十年子午门，见多识广。
"老周，"秦把总把图摊开，"你看这个圈——'乙'字在这儿，箭头指着两个圈。这意思是，瞧见'乙'，得同时往左走、又往右走？一个人，怎么同时走两条路？"
老周看了半晌，笑了："把总，您这话问得——咱们一支队伍验一块牌，只能走一条路。可咱们要是派两支队伍呢？"
"什么意思？"
"您想啊，"老周说，"牌上刻的字，是死的，一个字一个字念。咱们验牌的时候，每念一个字，就把现在'站在哪个圈上'的所有兵，都派出去走一遍——念到'乙'，站在'乙'这个圈上的兵，有两条路可走，那就让一半走左边、一半走右边。"
"那到最后，'落在打勾圈里'的兵，要是有任何一个——这块腰牌，就算合格。"
秦把总眼睛一亮："妙啊！一个人走不了两条路，那就派两个人；两个人不够，就派四个人——反正兵多，只要有一个兵走到'打勾'的圈里，就放行！"
"正是这个理。"老周说，"这叫'兵分多路'——咱不怕路多，就怕漏了该走的路。每块牌，把所有的路都走一遍，只要有一条走通，就算它合格。"
三、兵不够用了
夜巡队按"兵分多路"的法子验了半个月牌，倒也顺当。可有天晚上，来了麻烦。
那晚守门的兵只有十五个，却一连来了几十位要进城的贵人，腰牌上的字一个比一个绕。
验第一块牌，秦把总派了两个兵，走通了。
第二块，派了四个兵。
第三块，好家伙——图里的岔路太多，念到第五个字，已经有八个兵在同时走八条不同的路。念到第八个字，十六个兵都不够用了。
"把总，"老周皱眉，"这图上的岔路，多的离谱。一块牌念到一半，兵就分光了；下块牌，就只能干瞪眼。"
秦把总一拍大腿："这不行！兵是有数的，路是没数的——咱们不能'每块牌都把所有兵撒出去'。"
"可要是不撒，"老周说，"漏了路怎么办？"
秦把总在城楼上踱了半夜，忽然停下："老周，你说——这些兵，分成几路，是不是太多'重复'了？"
"怎么说？"
"你想，"秦把总指着图，"念到第五个字，八个兵走八条路——可这八条路里，有没有可能，有两条路'撞'到同一个圈上？两个兵站在同一个圈上，后头要走的字又是一样的——那这两个兵，是不是等于白派了一个？"
老周一拍脑门："还真是！咱俩守着图，把'所有可能站到的圈'记下来——结果发现，念到第八个字，虽然撒出去十六个兵，可他们站的圈，拢共就五个！十六个人，站在五个圈上——多余的人，全是白站！"
"那就好办了。"秦把总说，"咱们每块牌，不按'兵数'派，按'圈数'派——不管有多少兵，只要把'此刻可能站在哪几个圈上'记清楚，每个圈派一个兵，就够了！"
四、从"几条路"到"几个圈"
秦把总和老周连夜重画了一副"验牌图"。
新图跟老太监那张不一样了。老图里，一个圈能走两条路——岔路多、路数杂；新图里，他们把老图从头到尾重新捋了一遍，每念一个字，都把"此刻可能站到的所有圈"合成一个"大圈"，再从这个大圈往外画箭头。
"您看，"老周指着新图，"老图里'念甲→可到圈一，也可到圈二'；新图里，我画一个'大圈'，里头装着{圈一，圈二}——念甲，就直接进这个大圈。大圈之间，每念一个字，只走一条路。"
"念十个字，"秦把总问，"要走几条路？"
"还是十条——可这十条，每一条都是'一条箭头到一个大圈'，再也没有岔路。"老周说，"兵分几路？一路！一个兵，顺着大圈走到底，就行了。"
秦把总愣了："这……这不就跟'念'甲'字只能进一个圈'一样简单了？"
"对喽。"老周说，"把'一心想岔的'，变成'板上钉钉的'。 老太监那张图，是给人看的——画得明白，可能走的岔路多；咱们这张新图，是给兵用的——岔路全被'装进大圈'了，一个兵走到底，绝不含糊。"
"可是，"秦把总还有疑问，"大圈里装着好几个小圈，兵站进大圈，怎么知道'自己算走对没走对'？"
"大圈里只要装着任何一个'打勾'的小圈，"老周说，"这个大圈就算'打勾'——兵走到这儿，就算合格。"
秦把总长叹一声："妙。咱们兵少，可圈有数——不管腰牌上的字有多绕，'可能站到的圈'拢共就那么几个。兵不够不怕，把路'并'成圈，一条路，就顶十条路。"
五、子时三刻，一道令走到底
换上新图那晚，正好赶上中秋，贵人如潮。
夜巡队验牌，一个兵一块牌，顺着大圈走到底——没有岔路，没有分兵，快得像流水。
老太监半夜亲自来查岗，看见兵丁们验牌验得飞快，一块牌一眨眼的工夫就验完，惊得直咂嘴。
"把总，"老太监问，"我那张图，岔路多得我自个儿都数不清。你们是怎么做到'一条路走到底'的？"
秦把总把新图递过去："大人，您那张图，是'章程'——想的是周全，可守门的人看它，得一边走一边'想着岔路'，太累。我们这张图，是'令'——把您那章程里所有的岔路，全都'装进圈里'了。兵丁不用想，照着走，就是。"
老太监盯着新图看了半晌，忽然笑了：
"好一个'把岔路装进圈里'。你们这是……把一道'越想越多的令'，变成了一道'越走越少的令'。妙，妙啊。"
秦把总站在城楼上，望着子午门下川流不息的贵人，忽然对老周说：
"老周，你说咱们这新图，到底'新'在哪？"
"新在……"老周想了想，"旧图是'一条路一条路地想'，新图是'一堆路合成一个圈地走'。旧图怕路多，新图不怕——因为不管路有多少，圈的总数，是死的。"
"对。"秦把总说，"路是虚的，圈是实的。把虚的想明白了，化成实的——守门的人，就再也不用操心了。"
子时三刻，最后一拨贵人进了城。子午门的铜门缓缓合上，门缝里漏进来的月光，落在那张新画的图上——大圈套小圈，一笔一画，规规矩矩。
"路再多，也架不住'并圈'；题再绕，也绕不出'有限'。把天下的岔路都收进几只圈里——一道令，就能稳稳地走到底。"
技术解读
有限自动机（Finite Automaton）是编译原理与计算理论的基础概念。正则表达式可以描述"匹配模式"，而它的等价物正是有限自动机：NFA（Nondeterministic Finite Automaton，非确定有限自动机）与 DFA（Deterministic Finite Automaton，确定有限自动机）。两者的表达能力完全等价（Rabin & Scott，1959，因该成果获图灵奖），但行为迥异：NFA 在同一个输入下可能有多个转移选择（"岔路"），DFA 则每个状态每个输入恰好只有一个转移（"一条路走到底"）。
子集构造法（Subset Construction，Thompson 1968）是将 NFA 转换为等价 DFA 的标准算法：DFA 的每个状态是 NFA 状态集合的一个子集，代表"NFA 此刻可能处于的所有状态"。因为 NFA 的状态数有限，其子集数（2^N）虽然理论上指数级，但在实际正则表达式场景中通常远小于 2^N。词法分析器生成器（lex、flex、RE2C 等）正是用这个算法，把正则表达式编译成高效的 DFA 扫描器。
核心概念回顾
| 概念 | 通俗解释 |
|---|---|
| 有限自动机（FA） | 由有限个状态和转移规则构成的"机器"，用于识别/匹配字符串 |
| NFA（非确定有限自动机） | 同一输入可能有多个可选转移——"同时走几条路" |
| DFA（确定有限自动机） | 每个状态每个输入恰有一个转移——"一条路走到底" |
| 子集构造（Subset Construction） | 把 NFA 转换成等价 DFA 的算法：DFA 状态 = NFA 状态集合 |
| ε-转移（Epsilon Transition） | 不消耗输入就能跳转的边——"空走一步" |
| 接受状态（Accepting State） | 匹配成功的终止状态——"打勾的圈" |
| 状态集合（Set of States） | DFA 的一个状态对应 NFA 的一组状态——"大圈装小圈" |
| 正则表达式（Regex） | 描述字符串模式的记号语言，与有限自动机表达力等价 |
| 词法分析（Lexing） | 编译器的第一步：把源码拆成 token——词法分析器的核心就是自动机 |
| 等价性（Equivalence） | NFA 与 DFA 识别同一类语言——正则语言 |
| 状态爆炸（State Explosion） | 最坏情况下 DFA 状态数可达 2^N——但实际通常远小于此 |
| 最小化（Minimization） | 合并等价状态，得到状态数最少的 DFA |
故事中的隐喻对照
| 故事元素 | 映射的技术概念 | 解释 |
|---|---|---|
| 老太监画的验牌图 | NFA | 存在多个可选转移的自动机——"一个圈能走两条路" |
| "同时往两条路走"的圈 | NFA 的非确定性 | 同一输入下多个后继状态 |
| "兵分多路，一路走到打勾的圈" | NFA 的接受条件 | 存在一条从起始状态到接受状态的路径即匹配成功 |
| "兵不够用了"（岔路太多） | NFA 的模拟开销 | 直接模拟 NFA 需要同时追踪多个状态，成本高 |
| "把此刻可能站到的圈合成大圈" | 子集构造法 | DFA 状态 = NFA 状态集合 |
| "每念一个字只走一条路" | DFA 的确定性 | 每个状态每个输入恰有一个转移 |
| "一个兵顺着大圈走到底" | DFA 的线性扫描 | 匹配复杂度 O(n)，与字符串长度成正比 |
| "大圈里装着打勾的小圈即合格" | 接受状态集合的判定 | DFA 状态包含任一 NFA 接受状态即为接受态 |
| "圈的总数是死的" | 状态数的有限性 | NFA 状态有限 ⇒ 子集数量有限（即使理论上 2^N） |
| "旧图是章程，新图是令" | 正则表达式 vs 编译后的 DFA | 正则模式用 NFA 表达（人读），词法分析器用 DFA 执行（机器跑） |
| 夜巡队一个兵验一块牌 | 词法分析器的扫描 | 编译器中正则匹配的工程实现 |
为什么这个故事对应 NFA→DFA 子集构造？
- 正则表达式天然对应 NFA。 正则的"或""重复"等构造会让匹配过程出现多种可能路径——这正是 NFA 的非确定性。老太监的图（NFA）忠实表达了规则，但难以直接高效执行。
- NFA 模拟开销随分支增长。 直接模拟 NFA 需并行追踪所有可能状态，分支多时成本陡增——"兵不够用了"精确对应 NFA 模拟的最坏情况 O(N×M)。
- 子集构造用"状态集合"消除不确定性。 DFA 的每个状态记录"NFA 此刻可能处于的所有状态"——把"同时走几条路"变成"站在一个装着小圈的圈里"，岔路被显式合并。这是算法的核心思想。
- DFA 的执行是线性的。 转换后，匹配只需从头到尾扫一遍输入，每步一个确定转移——"一个兵走到底"。这正是词法分析器追求的高效性。
- 等价性是理论基础。 NFA 与 DFA 识别完全相同的语言（正则语言）——故事里新旧图"验的牌一样"，正是"等价转换"的体现。Rabin & Scott 的证明保证了转换不改变匹配能力。
- 状态爆炸的实用警示。 理论上子集构造可能产生 2^N 个状态，但实际正则中几乎不会发生——"圈的总数是死的"，这句话既是对有限性的肯定，也隐含了对状态爆炸的警惕。
后记：子午门的夜巡队教会我们的，是一种"把不确定变成确定"的工程智慧：与其让每个人都时刻想着"接下来该走哪条路"，不如把所有可能的路，预先收进几只圈里——从此，一道令稳稳地走到底。NFA 是思想的自由，DFA 是执行的确定；子集构造，就是两者之间那座朴素的桥。路再多，也架不住"并圈"——把天下的岔路都收进有限几只圈里，再复杂的事，也能变成一步一个脚印的坦途。
