文章目录
一、正则表达式转为非确定性有限自动机 NFA 要点
二、正则表达式转为非确定性有限自动机 NFA 示例 1
三、正则表达式转为非确定性有限自动机 NFA 示例 2
四、正则表达式转为非确定性有限自动机 NFA 示例 3
一、正则表达式转为非确定性有限自动机 NFA 要点
正则表达式转为非确定性有限自动机 NFA 流程 :
① 原子自动机 : 首先要构造 原子自动机 , 从 非接受状态 指向 接受状态 ;
② 基本拼装 : 将原子自动机进行 基本的拼装 , 并运算 , 交运算 ;
③ 复杂拼装 : 将 基本拼装的自动机 进行 进一步拼装 ;
拼装原则 : 使用 ε \varepsilonε 箭头 进行拼装 ;
① 串联 : 前者的接受状态 使用 ε \varepsilonε 箭头 指向 后者的开始状态 , 前者接受状态取消 ; 如果有两个接受状态 , 那么就需要引出两个箭头
② 并联 : 在二者之前 , 重新添加一个非接受状态的开始状态 , 使用两个 ε \varepsilonε 箭头 分别指向二者的开始状态 ;
③ 星运算 : 重新添加一个接受状态的开始状态 , 使用 ε \varepsilonε 箭头从 接受状态 指向 开始状态 ; 注意所有的接受状态 , 都要使用 ε \varepsilonε 箭头指向开始状态 ;
二、正则表达式转为非确定性有限自动机 NFA 示例 1
将正则表达式 ( 0 ∪ 1 ) ∗ 000 ( 0 ∪ 1 ) ∗ \rm (0 \cup 1)^*000 ( 0 \cup 1 )^*(0∪1)
∗
000(0∪1)
∗
转为 NFA ;
构造原子自动机 : 注意从 非接受状态 → \to→ 接受状态 ;
( 0 ∪ 1 ) \rm (0 \cup 1)(0∪1) 并联拼装 : 在二者前面添加 非接受状态 起始状态 ;
( 0 ∪ 1 ) ∗ \rm (0 \cup 1)^*(0∪1)
∗
星运算 : 使 接受状态 → \to→ 起始状态 , 并添加一个 接受状态 起始状态 , 指向原来的起始状态 ;
000 000000 串联 : 前者的接受状态 必须转为 非接受状态 , 前者的接受状态 必须转为 非接受状态 , 后者的状态是不变的 ;
总拼装 :
串联注意事项 : ( 0 ∪ 1 ) ∗ \rm (0 \cup 1)^*(0∪1)
∗
有 3 33 个接受状态 , 需要引出 3 33 个 ε \varepsilonε 箭头 指向 000 000000 代表的自动机 的 开始状态 ;
串联时的状态改变 : 使用 ε \varepsilonε 箭头 连接 前者的接受状态 → \to→ 后者的起始状态;
串联时 前者的接受状态 必须转为 非接受状态 ,
后者的状态是不变的 , 如果是接受状态 , 那么就保持接受状态不变 , 同理如果是非接受状态 , 那么保持非接受状态不变 ;
化简后结果 :
