软件开发中的非确定性有限状态机？

Question

最近我一直在考虑有限状态机(FSM),以及如何在软件中实现它们(编程语言并不重要).

我的理解是确定性状态机被广泛使用(解析/词法分析器,编译器等),但是非确定性状态机的问题是什么？

我知道可以将所有非确定性状态机转换为确定性状态机(甚至是以编程方式).那不是我的观点.我还想象非确定性状态机实现起来要复杂得多.

总之,它使任何意义上实现非确定性状态机？有什么特别的应用我不知道吗？这可能是什么原因？也许优化和专业的非确定性状态机更快？

Answer 1

大多数正则表达式引擎使用非确定性自动机,因为它们提供了更大的灵活性.DFA受到更多限制.看看一些实现,你会看到这一点.微软甚至在他们的.NET Regex类文档中强调了这一事实:

.NET Framework正则表达式引擎是一种回溯正则表达式匹配器,它包含传统的非确定性有限自动机(NFA)引擎,例如Perl,Python,Emacs和Tcl使用的引擎.

匹配行为(第一段) - 本文还提供了使用NFA而不是更有效的DFA的基本原理.

Answer 2

如您所知,NFA和DFA在计算上是等效的.这是自动机理论中的第一个定理之一.有一些算法可以将一个转换为另一个(与Pushdown或图灵机不同).

所以.为什么一个超过另一个？因为使用NFA表示给定问题比等效DFA容易得多.

编辑:就实际计算机器而言,DFA会更快,因为它们不必回溯.但他们将需要更多的记忆来代表.(Mem与CPU权衡)