为什么 NFA 中使用 epsilon 转换？

Question

我试图了解如何从正则表达式创建 NFA-s，但我对 epsilon 转换感到非常困惑。我的教科书中有这个例子，但我不明白为什么使用 epsilon 转换以及如何知道何时使用它们。

Answer 1

一般来说，espilon 转换在方便时使用。例如，当从正则表达式构建 NFA 时，首先构建与表达式部分相对应的自动机的小部分。要连接它们，您需要进行转换。但是，如果那里没有要读取的符号，则 epsilon 转换是执行此操作的简单方法。然而它们并不是必需的，您总能找到没有它们的解决方案。

在您的示例中，只需应用教科书中描述的算法即可。它告诉您何时使用它们。

epsilon 跃迁

• 从 1 到 2 可能连接 (a|b)* 和 ac 的部分
• 1->5 和 8->1 可能是 * 的结果
• 5->6 和 5->7 可能是 | 中的替代方案的结果