解释带有 ε 转移的 NFA。

我们通过允许瞬时 ε 转移来扩展 NFA 的类别。

自动机可能允许在不读取输入符号的情况下更改其状态。

在图中，这种转移通过用 ε 标记相应的弧来表示。

注意，这并不意味着 E 成为输入符号。相反，我们假设符号 E 不属于任何字母表。

  • ε-NFA 添加了一个方便的功能，但（从某种意义上说）它们并没有给我们带来任何新东西。它们并没有扩展可以表示的语言的类别。
  • NFA 和 ε-NFA 都识别完全相同的语言。

Epsilon (ε) - 闭包

对于给定状态 X，Epsilon 闭包是从状态 X 出发，仅通过（空）或 ε 移动（包括状态 X 本身）可以到达的状态集。

换句话说，状态的 ε-闭包可以通过递归地对从 X 出发通过单个 ε 移动可以到达的状态的 ε-闭包进行并集运算来获得。

示例

考虑以下带有 ε 移动的 NFA 图：

上述 NFA 的状态转移表如下：

状态01epsilon
AB,CAB
B-BC
CCC-

对于上述示例，ε 闭包如下：

  • ε 闭包(A) : {A, B, C}
  • ε 闭包(B) : {B, C}
  • ε 闭包(C) : {C}

更新于：2021年6月12日

24K+ 次查看

开启你的职业生涯

完成课程获得认证

开始学习
广告