如果 NFA 和 DFA 是等价的，为什么我们会有两个正则表达式引擎？
If NFA and DFA were equivalent, why would we have two engines for regex?
来自掌握正则表达式3e:
As a result, broadly speaking, there are three types of regex engines:
- DFA (POSIX or not—similar either way)
- Traditional NFA (most common: Perl, .NET, PHP, Java, Python, . . . )
- POSIX NFA
来自计算理论：形式语言、自动机和复杂性：
For each NFA, there is a DFA that accepts exactly the same language.
我能说 NFA 和 DFA 是一回事吗？或者即使他们识别模式的能力相当，但他们在某些方面仍然不同？
您缺少两件事：
"traditional NFA" 实现实际上包括超出 NFA 的严格计算机科学定义的能力。
性能特征是一个值得关注的问题，即使给出两个涵盖相同答案的实现也是如此。
最终效果是回溯实现（我比 "traditional NFA" 更喜欢这个名字）比 DFA 实现稍微更具表现力，因为它们可以匹配像 (\w{3,}) 这样的正则表达式，匹配三个或更多单词字符重复两次（DFA 无法匹配的东西）。同时，DFA 实现的输入长度保证为 O(n)，但很容易编写具有 O(n^2) 或更糟糕的行为的正则表达式，当出现它们不匹配的字符串时。 （见 https://swtch.com/~rsc/regexp/regexp1.html ）
来自掌握正则表达式3e:
As a result, broadly speaking, there are three types of regex engines:
- DFA (POSIX or not—similar either way)
- Traditional NFA (most common: Perl, .NET, PHP, Java, Python, . . . )
- POSIX NFA
来自计算理论：形式语言、自动机和复杂性：
For each NFA, there is a DFA that accepts exactly the same language.
我能说 NFA 和 DFA 是一回事吗？或者即使他们识别模式的能力相当，但他们在某些方面仍然不同？
您缺少两件事：
"traditional NFA" 实现实际上包括超出 NFA 的严格计算机科学定义的能力。
性能特征是一个值得关注的问题，即使给出两个涵盖相同答案的实现也是如此。
最终效果是回溯实现（我比 "traditional NFA" 更喜欢这个名字）比 DFA 实现稍微更具表现力，因为它们可以匹配像 (\w{3,}) 这样的正则表达式，匹配三个或更多单词字符重复两次（DFA 无法匹配的东西）。同时，DFA 实现的输入长度保证为 O(n)，但很容易编写具有 O(n^2) 或更糟糕的行为的正则表达式，当出现它们不匹配的字符串时。 （见 https://swtch.com/~rsc/regexp/regexp1.html ）