automata - NFA 和 epsilon NFA 的实例

Question

NFA 和 epsilon NFA 的实时示例是什么，即除了它用于设计编译器之外的实际示例

Answer 1

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

实际上，今天的正则表达式引擎已经超越了这些数学概念，并添加了一些功能，这些功能允许做的事情超出了 FA 允许的范围。然而，许多正则表达式不使用这些功能，或者以有限的方式使用它们，以至于可以使用 FA 来实现它们。

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

Answer 2

让我们不要忘记基本基于有限自动机的马尔可夫链。结合bellpeace提到的硬件和软件建模，一个非常强大的工具。

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

Answer 3

一个有点晦涩但有效的例子是aho-corasick 算法，它使用有限自动机在文本中搜索多个字符串

Answer 4

正如@delnan 所解释的，自动机通常以正则表达式的形式使用。但是，它们的用途不止于此。自动机通常用于对硬件和软件系统进行建模并验证它们的某些属性。您可以通过查看模型检查找到更多信息。在介绍自动机、语言和计算的介绍中可以找到一个非常简单的激励示例。