构造正则语言 L = (00)*1(11)* 的 ∈-NFA

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

ε-NFA 用五元组表示法定义

{Q, q0, Σ, δ, F}

其中，

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

  • Q − 有限状态集

  • Σ − 有限输入符号集

  • q0 − 初始状态

  • F − 终结状态

  • δ − 转移函数

无 ε 转移的 NFA

NFA 也具有与 DFA 相同的五个状态，但具有不同的转移函数，如下所示：

$$\delta\colon\:Q\times\:\sum\longrightarrow\:2^{Q}$$

其中，

  • Q：有限状态集

  • Σ：有限输入符号集

  • q0：初始状态

  • F：终结状态

  • δ：转移函数

让我们考虑给定的语言 L = (00)*1(11)*。

给定的语言分为三个部分 (00)*、1 和 (11)*。让我们为每个部分构建状态转换图，最后将这三个部分连接起来以获得最终结果。

**步骤 1** - (00)* 的带 epsilon 的 NFA 如下：

**步骤 2** - (11)* 的带 epsilon 的 NFA 如下：

**步骤 3** - 将第一部分和第二部分与中间的 1 连接起来，如下所示：

更新于：2021年6月14日

2K+ 浏览量

开启你的 职业生涯

完成课程获得认证

开始学习
广告