自动机

正则表达式引擎深度工程实战:从回溯陷阱、Lazy DFA 到 SIMD 预过滤与 Hyperscan 流模式

拆解现代正则表达式引擎的完整工程链路:回溯为何指数爆炸、Thompson NFA 如何给出线性保证、Lazy DFA 怎样用状态预算对抗状态爆炸、Pike VM 如何同时承担捕获组与 leftmost-first 语义、Rust regex meta engine 的多机降级、Teddy/PSHUFB 的 3 指令 SIMD 预过滤,以及 Hyperscan 的 streaming mode、FDR 字面量合并与 SOM 代价,最后给出生产落地清单。

乔姆斯基谱系与形式语言深度实战:从正则语言、上下文无关文法与 CYK 解析到图灵机与计算理论边界的完整工程链路

形式语言与自动机理论是计算机科学最底层的"语法宪法"——它规定了什么样的问题能被机器描述、被多强的机器识别,以及识别成本的下界。诺姆·乔姆斯基(Noam Chomsky)在 1956 年提出的**谱系(Chomsky Hierarchy)**把语言按生成能力分成四类,对应从有限状态机到图灵机的四档算力。这篇文章不走教科书式的纯证明路线,而是把每一层都用**可运行的 Python** 落一遍:手写 …