最近我一直在思考有限状态机（FSMs），以及我如何在软件中实现它们（编程语言并不重要）。
我的理解是，确定性有限状态机广泛应用于解析器/词法分析器、编译器等领域，但是非确定性有限状态机有什么问题呢？
我知道可以将所有非确定性有限状态机转换为确定性有限状态机（甚至可以通过编程实现）。这不是我的重点。我也想象到，非确定性有限状态机实现起来要复杂得多。
无论如何，实现非确定性有限状态机有任何意义吗？有我不知道的任何特殊应用吗？有哪些原因可以这样做？也许优化和专门的非确定性有限状态机更快？
软件开发中的非确定性有限状态机？
8
- Christoph Schiessl
1
1语言确实很重要，因为它需要是图灵完备的。 - jjnguy
8个回答
6
正如您所知，NFA和DFA在计算上是等效的。这是自动机理论中的第一个定理之一。有算法将一个转换为另一个（与下推或图灵机不同）。
那么，为什么选择其中一个？因为使用NFA表示给定问题比等效的DFA更容易。
编辑：就实际计算机而言，DFA会更快，因为它们不必回溯。但是它们需要更多的内存来表示。（内存与CPU之间的权衡）
那么，为什么选择其中一个？因为使用NFA表示给定问题比等效的DFA更容易。
编辑：就实际计算机而言，DFA会更快，因为它们不必回溯。但是它们需要更多的内存来表示。（内存与CPU之间的权衡）
- Vlion
3
同意。但请尝试自己实现状态机 - 在这方面，非确定性状态机要复杂得多。你觉得呢？ - Christoph Schiessl
DFAs会更快，因为它们不需要回溯。但是它们将需要更多的内存来表示。（内存与CPU之间的权衡） - Paul Nathan
1由于可能存在歧义，使用DFA无法可靠地找到子表达式的开头和结尾，因此需要回溯。这就是为什么所有这些语言都使用NFA的原因。 - Meinersbur
1
我的建议是：看一下Adrian Thurstons Ragel的手册。
有简单的方法可以直接生成DFA，但我认为它们只支持有限范围的运算符 - 基本上是EBNF中常见的操作符。Ragel使用非确定性方法从简单的自动机组合成复杂的自动机，然后使用epsilon消除和最小化来创建高效的确定性自动机。无论您需要多少奇怪的运算符，转换为最小确定性自动机始终是相同的，并且每个运算符实现都通过使用非确定性方法保持简单。
- user180247
0
通常创建一个NFA然后使用它会更容易（唯一的区别是你持有一组状态而不是一个状态）。如果你想要快速，可以制作DFA，但不要忘记，这样做的时间是指数级的（因为结果自动机可能会指数级增长！）。
另一方面，如果你想要创建一个补充语言，你没有选择，你需要一个确定性变量。
这就是为什么否定在正则表达式引擎中不存在的原因，只存在于类（[^...]）中，在那里你可以确信自动机是确定性的。
- hypiz
0
如果我错了，请纠正我，但是从我的编译器课程中我记得有时候你根本不能使用DFA，因为它会导致状态的“爆炸”。
- Blago
0
我认为选择非确定性有限状态自动机的主要原因是为了实际获取所选匹配项。使用确定性版本可能更难做到这一点。
如果您只想知道它们是否匹配，而不需要其他细节，那么将其编译为有限自动机可能会更好。
如果您只想知道它们是否匹配，而不需要其他细节，那么将其编译为有限自动机可能会更好。
- Bill Lynch
0
Cayuga在复杂事件处理方面使用了非确定性有限状态机。看起来他们称之为“具有状态的发布/订阅事件监控”，但我认为这是CEP。
我相信他们的一些论文甚至讨论了为什么要使用自动机模型。你可能想在他们的网站上找找。
...... Cayuga自动机，扩展自标准的非确定性有限自动机。
- Thomas Owens
3
作为后续，我仍然想要一个像我在这里指出的那样的系统，并制作一些普通人可以使用的酷东西...但是我很懒。 - Thomas Owens
Cayuga 自动机不等同于 NFA。它是一种修改，旨在接近 NFA 的行为。 - oz10
“从标准的非确定有限自动机扩展而来”意味着他们从一个NFA开始，并对其进行了修改。 - Thomas Owens
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接