数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学构造正则语言 L = (0+1)*(00+ 11) 的 ∈-NFA
非确定有限自动机 (NFA) 中的 ε 转移用于在没有来自输入集 Σ 的任何符号的情况下从一个状态移动到另一个状态。
ε-NFA 定义为五元组
{Q, q0, Σ, δ, F}其中，
δ − Q × (Σ∪ε)→2Q
Q − 有限状态集
Σ − 有限输入符号集
q0 − 初始状态
F − 终结状态
δ − 转移函数
没有 ε 转移的 NFA
NFA 以 5 元组表示法定义
{Q, q0, Σ, δ, F}其中，
δ − Q X Σ→ 2Q
Q − 有限状态集
Σ, − 有限输入符号集
q0 − 初始状态
F − 终结状态
δ − 转移函数
NFA 和带有 epsilon 的 NFA 几乎相同；唯一的区别在于它们的转移函数。
让我们考虑给定的语言 L = 0(0+1)*1
构造 ε-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+1)*(00 + 11) 的 ε-NFA
L = (0+1)*(00 + 11) 分为两部分：(0+1)* 和 (00+11)。
首先构造第一部分，然后构造第二部分，最后连接这两部分以获得结果。
第一部分 − (0+1)*
借助步骤 3，我们可以轻松地构造 (0+1)*，如下所示：
第二部分 − (00+11)
第二部分可以借助步骤 4 轻松绘制。
在步骤 4 中，考虑 1 和 0 都是 00 或 11。这两个字符串由 + 符号连接。
最终带有 epsilon 移动的 NFA 如下：
连接第一部分和第二部分，
更新于： 2021年6月14日
17K+ 次查看
广告