DFA与NFA引擎:它们的功能和局限性有什么区别? [英] DFA vs NFA engines: What is the difference in their capabilities and limitations?

问题描述

我正在寻找基于DFA和NFA引擎之间功能和局限性的非技术性解释.

I am looking for a non-technical explanation of the difference between DFA vs NFA engines, based on their capabilities and limitations.

推荐答案

确定性有限自动机(DFAs)和非确定性有限自动机(NFA)具有完全相同的功能和局限性.唯一的区别是符号方便.

Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) have exactly the same capabilities and limitations. The only difference is notational convenience.

有限自动机是具有状态并读取输入的处理器，每个输入字符都有可能将其设置为另一状态.例如，一个状态可能是连续读取两个C"或一个单词开始读".这些通常用于快速扫描文本以找到模式，例如对源代码进行词法扫描以将其转换为令牌.

A finite automaton is a processor that has states and reads input, each input character potentially setting it into another state. For example, a state might be "just read two Cs in a row" or "am starting a word". These are usually used for quick scans of text to find patterns, such as lexical scanning of source code to turn it into tokens.

确定性有限自动机一次处于一种状态，这是可以实现的.一个不确定的有限自动机一次可以处于一个以上的状态:例如，在一种标识符可以以数字开头的语言中，可能存在一个读取数字"状态和另一个读取标识符"状态，并且当读取以"123"开头的内容时，NFA可能同时处于两个位置.实际适用哪种状态取决于在单词结尾之前是否遇到了非数字的东西.

A deterministic finite automaton is in one state at a time, which is implementable. A nondeterministic finite automaton can be in more than one state at a time: for example, in a language where identifiers can begin with a digit, there might be a state "reading a number" and another state "reading an identifier", and an NFA could be in both at the same time when reading something starting "123". Which state actually applies would depend on whether it encountered something not numeric before the end of the word.

现在，我们可以将读取数字或标识符"表示为状态本身，突然之间，我们不需要NFA.如果我们将NFA中的状态组合表示为状态本身，则DFA包含的状态要比NFA多得多，但是这样做是相同的.

Now, we can express "reading a number or identifier" as a state itself, and suddenly we don't need the NFA. If we express combinations of states in an NFA as states themselves, we've got a DFA with a lot more states than the NFA, but which does the same thing.

这是一个更容易阅读或书写或处理的问题. DFA本身更容易理解，但NFA通常较小.

It's a matter of which is easier to read or write or deal with. DFAs are easier to understand per se, but NFAs are generally smaller.

这篇关于DFA与NFA引擎:它们的功能和局限性有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！