我正在寻找DFA和NFA引擎之间基于功能和局限性的非技术性解释。
最佳答案
确定性有限自动机(DFA)和非确定性有限自动机(NFA)具有完全相同的功能和局限性。唯一的区别是符号方便。
有限自动机是具有状态并读取输入的处理器，每个输入字符都有可能将其设置为另一状态。例如，状态可能是“连续读取两个C”或“一个单词开始读”。这些通常用于快速扫描文本以找到模式，例如对源代码进行词法扫描以将其转换为标记。
确定性有限自动机一次处于一种状态，这是可以实现的。一个不确定的有限自动机一次可以处于一个以上状态:例如，在一种标识符可以以数字开头的语言中，可能存在一个状态“正在读取数字”和另一个状态“正在读取标识符”，并且当读取以“123”开头的内容时，NFA可能同时处于两个位置。实际适用的状态取决于在单词结尾之前是否遇到了非数字的东西。
现在，我们可以将“读取数字或标识符”表示为状态本身，突然之间，我们不需要NFA。如果我们将NFA中的状态组合表示为状态本身，则DFA包含的状态要比NFA多得多，但是这样做的作用相同。
这是一个更容易阅读或编写或处理的问题。 DFA本身更容易理解，但NFA通常较小。
关于regex - DFA与NFA引擎:它们的功能和局限性有什么区别？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3978438/