NFA和epsilon NFA的实际示例

Question

NFA和epsilon NFA的实时示例是什么，即在设计编译器时使用的其他实际示例

Answer 1

任何时候任何人使用正则表达式，他们都是在使用有限自动机。如果您不太了解正则表达式，让我告诉您它们非常常见--在许多生态系统中，当面临从字符串中提取结构化数据时，它是大多数人尝试应用的第一个工具。理解自动机是理解(和推理)正则表达式的一种方法，如果你有数学倾向，这也是一种非常可行的方法。

实际上，今天的正则表达式引擎已经超越了这些数学概念，并添加了允许执行超过FA所允许的功能的功能。然而，许多正则表达式并不使用这些特性，或者以一种非常有限的方式使用它们，因此可以使用FA来实现它们。

现在，我之前只谈到了有限自动机。NFA是特定的FA，就像DFA一样，两者可以相互转换(从技术上讲，任何DFA都已经是NFA)。因此，虽然你可以在上面用" NFA“替换”有限自动机“，但要注意，它不一定是引擎盖下的NFA。

Answer 2

就像@delnan解释的那样，自动机通常以正则表达式的形式使用。然而，它们的使用远不止于此。自动机通常用于对硬件和软件系统建模，并验证它们的某些属性。你可以通过查看model checking找到更多信息。在Introduction to Automata, Languages, and Computation的介绍中可以找到一个真正简化的激励示例。

Answer 3

让我们不要忘记Markov chains，它基本上也是基于有限自动机的。结合贝尔和平提到的硬件和软件建模，这是一个非常强大的工具。

如果你想知道为什么epsilon NFA被认为是NFA的一种变体，那么我认为没有充分的理由。它们以相同的方式解释，除了每一步可能不再是单位时间，但NFA也不是真正的单位时间。