交互式演示：NFA 引擎是如何工作的
💡
原文中文，约600字，阅读约需2分钟。
📝
内容提要
正则表达式被视为“黑盒”，使用非确定性有限自动机（NFA）进行匹配。通过交互演示，可以直观理解其并行特性和状态转移过程。每次点击“下一步”，引擎读取字符并检查状态集合，形成新的状态集合。NFA的并行特性使其在匹配时能同时尝试多条路径，从而确保线性时间复杂度。
🎯
关键要点
- 正则表达式被视为一个“黑盒”，输入规则和文本后返回匹配结果。
- 内部使用非确定性有限自动机（NFA）进行匹配，具有并行特性。
- 通过交互演示可以直观理解NFA的状态转移过程。
- 点击“编译并重置”将正则表达式转换为NFA图。
- NFA从起始节点开始，通过$ ext{ε}$边计算初始状态集合。
- 每次点击“下一步”时，引擎读取字符并检查状态集合。
- 如果状态能接受字符，则转移到下一个状态，形成新的状态集合。
- NFA的并行特性使其能同时尝试多条路径，类似于量子力学中的“叠加态”。
- NFA引擎（如RE2）能保证线性时间复杂度，无需回溯。
➡️
