构建一个用于语言 L = (a* + b*) 的 ∈-NFA。

非确定性有限自动机 (NFA) 中的 ε 转移用于在没有来自输入集 Σ 的任何符号的情况下从一个状态移动到另一个状态。

ε-NFA 以五元组表示法定义。

{Q, q0, Σ, δ, F}

其中，

  • δ − Q × (Σ∪ε)→2Q

  • Q − 有限状态集

  • Σ − 有限的输入符号集

  • q0 − 初始状态

  • F − 终结状态

  • δ − 转移函数

没有 ε 转移的 NFA

NFA 以五元组表示法定义。

{Q, q0, Σ, δ, F}

其中，

  • δ − Q X Σ→ 2Q

  • Q − 有限状态集

  • Σ − 有限的输入符号集

  • q0 − 初始状态

  • F − 终结状态

  • δ − 转移函数

NFA 和带有 epsilon 的 NFA 几乎相同；唯一的区别在于它们的转移函数。

让我们考虑给定的语言 L = (a*+b*)

构建 ε-NFA 的步骤

步骤 1 − a* 的带 epsilon 的 NFA 如下所示 −

a* 表示表达式中可以有任意数量的“a”，甚至 0（如果输入符号为空，则它也有效）。

步骤 2 − b* 的带 epsilon 的 NFA 如下所示 −

b* 表示表达式中可以有任意数量的 b，甚至 0（如果输入符号为空，则它也有效）。

步骤 3 − 现在使用第一步和第二步构建 a*+b*。

给定的语言被分成两部分，如 a* 和 b*，并使用“+”符号添加两个步骤以获得结果。

更新于: 2021年6月14日

4K+ 阅读量

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告