数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究构造正则语言L = 0(0+1)*1 的 ∈-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 − 终结状态
δ − 转移函数
示例
考虑如下具有 ε 的 NFA：
这里 q0 是一个起始状态，输入 0，可以处于状态 q0 或状态 q1。
如果我们得到起始符号 1，则通过 epsilon 转移，我们可以将状态从 q0 更改为 q1，然后输入 1 可以处于状态 q1。
另一方面，从状态 q0 输入 1，我们可以到达状态 q2。
因此，输入 1 后是否会处于状态 q1 或 q2 尚不确定。
因此，它被称为非确定性有限自动机，并且由于有一些 epsilon 移动，我们可以简单地将状态从一个状态更改为另一个状态。
因此，它被称为带有 epsilon 的 NFA。
让我们考虑给定的语言 L = 0(0+1)*1。
构造 ε-NFA
构造 ε-NFA 的步骤如下：
步骤 1 - 0+ 的带有 epsilon 的 NFA 如下：
步骤 2 - 0* 的带有 epsilon 的 NFA 如下：
步骤 3 - (0+1) 的带有 epsilon 的 NFA 如下：
上述状态转换图接受 0 或 1 作为输入。这两条路径都通向最终状态。
步骤 4 - 01 的带有 epsilon 的 NFA 如下：
对于串联，0 必须后跟 1。
步骤 5 - L = 0(0+1)*1 的 ε-NFA 如下：
L = 0(0+1)*1 分为三部分：0、(0+1)* 和 1。第二部分 (0+1)* 如上所述构造，只需与 0 和 1 串联，然后遵循第二个规则 0*。
最终带有 epsilon 移动的 NFA 如下：
8K+ 次浏览
