文章目录

• 一、正则表达式转为非确定性有限自动机 NFA 要点
• 二、正则表达式转为非确定性有限自动机 NFA 示例 1
• 三、正则表达式转为非确定性有限自动机 NFA 示例 2
• 四、正则表达式转为非确定性有限自动机 NFA 示例 3

一、正则表达式转为非确定性有限自动机 NFA 要点

---

正则表达式转为非确定性有限自动机 NFA 流程 :

① 原子自动机 : 首先要构造 原子自动机 , 从 非接受状态 指向 接受状态 ;

② 基本拼装 : 将原子自动机进行 基本的拼装 , 并运算 , 交运算 ;

③ 复杂拼装 : 将 基本拼装的自动机 进行 进一步拼装 ;

拼装原则 : 使用 $\epsilon$ 箭头 进行拼装 ;

① 串联 : 前者的接受状态 使用 $\epsilon$ 箭头 指向 后者的开始状态 , 前者接受状态取消 ; 如果有两个接受状态 , 那么就需要引出两个箭头

② 并联 : 在二者之前 , 重新添加一个非接受状态的开始状态 , 使用两个 $\epsilon$ 箭头 分别指向二者的开始状态 ;

③ 星运算 : 重新添加一个接受状态的开始状态 , 使用 $\epsilon$ 箭头从 接受状态 指向 开始状态 ; 注意所有的接受状态 , 都要使用 $\epsilon$ 箭头指向开始状态 ;

二、正则表达式转为非确定性有限自动机 NFA 示例 1

---

将正则表达式 $(0\cup 1{)}^{\ast }000(0\cup 1{)}^{\ast }$ 转为 NFA ;

构造原子自动机 : 注意从 非接受状态 $\to$ 接受状态 ;

$(0\cup 1)$ 并联拼装 : 在二者前面添加 非接受状态 起始状态 ;

$(0\cup 1{)}^{\ast }$ 星运算 : 使 接受状态 $\to$ 起始状态 , 并添加一个 接受状态 起始状态 , 指向原来的起始状态 ;

$000$ 串联 : 前者的接受状态 必须转为 非接受状态 , 前者的接受状态 必须转为 非接受状态 , 后者的状态是不变的 ;

总拼装 :

串联注意事项 : $(0\cup 1{)}^{\ast }$ 有 $3$ 个接受状态 , 需要引出 $3$ 个 $\epsilon$ 箭头 指向 $000$ 代表的自动机 的 开始状态 ;

串联时的状态改变 : 使用 $\epsilon$ 箭头 连接 前者的接受状态 $\to$ 后者的起始状态;

串联时 前者的接受状态 必须转为 非接受状态 ,

后者的状态是不变的 , 如果是接受状态 , 那么就保持接受状态不变 , 同理如果是非接受状态 , 那么保持非接受状态不变 ;

化简后结果 :

三、正则表达式转为非确定性有限自动机 NFA 示例 2

---

将正则表达式 $(((00{)}^{\ast }(11))\cup 01{)}^{\ast }$ 转为 NFA ;

构造原子自动机 : 注意从 非接受状态 $\to$ 接受状态 ;

$00$ 串联 : 前者的接受状态 必须转为 非接受状态 , 前者的接受状态 必须转为 非接受状态 , 后者的状态是不变的 ;

$(00{)}^{\ast }$星运算 : 使 接受状态 $\to$ 起始状态 , 并添加一个 接受状态 起始状态 , 指向原来的起始状态 ;

$11$ 串联 : 前者的接受状态 必须转为 非接受状态 , 前者的接受状态 必须转为 非接受状态 , 后者的状态是不变的 ;

$((00{)}^{\ast }(11))$ 串联 : 前者的接受状态 必须转为 非接受状态 , 前者的接受状态 必须转为 非接受状态 , 后者的状态是不变的 ;

$((00{)}^{\ast }(11))\cup 01$ 并联 : 在二者前面添加 非接受状态 起始状态 ;

$(((00{)}^{\ast }(11))\cup 01{)}^{\ast }$ 星运算 : 使 接受状态 $\to$ 起始状态 , 并添加一个 接受状态 起始状态 , 指向原来的起始状态 ;

化简后结果 :

四、正则表达式转为非确定性有限自动机 NFA 示例 3

---

将正则表达式 ${\varnothing }^{\ast }$ 转为 NFA ;

${\varnothing }^{\ast }$ $=\{\epsilon \}$

构造原子自动机 : 注意从 非接受状态 $\to$ 接受状态 ;

总结

以上是生活随笔为你收集整理的【计算理论】计算理论总结 ( 正则表达式转为非确定性有限自动机 NFA | 示例 ) ★★的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。