三、正则表达式转为非确定性有限自动机 NFA 示例 2
将正则表达式 ( ( ( 00 ) ∗ ( 11 ) ) ∪ 01 ) ∗ \rm ( ( (00) ^* (11) ) \cup 01 )^*(((00)
∗
(11))∪01)
∗
转为 NFA ;
构造原子自动机 : 注意从 非接受状态 → \to→ 接受状态 ;
00 0000 串联 : 前者的接受状态 必须转为 非接受状态 , 前者的接受状态 必须转为 非接受状态 , 后者的状态是不变的 ;
( 00 ) ∗ (00)^*(00)
∗
星运算 : 使 接受状态 → \to→ 起始状态 , 并添加一个 接受状态 起始状态 , 指向原来的起始状态 ;
11 1111 串联 : 前者的接受状态 必须转为 非接受状态 , 前者的接受状态 必须转为 非接受状态 , 后者的状态是不变的 ;
( ( 00 ) ∗ ( 11 ) ) ((00)^* (11))((00)
∗
(11)) 串联 : 前者的接受状态 必须转为 非接受状态 , 前者的接受状态 必须转为 非接受状态 , 后者的状态是不变的 ;
( ( 00 ) ∗ ( 11 ) ) ∪ 01 ((00)^* (11)) \cup 01((00)
∗
(11))∪01 并联 : 在二者前面添加 非接受状态 起始状态 ;
( ( ( 00 ) ∗ ( 11 ) ) ∪ 01 ) ∗ (((00)^* (11)) \cup 01)^*(((00)
∗
(11))∪01)
∗
星运算 : 使 接受状态 → \to→ 起始状态 , 并添加一个 接受状态 起始状态 , 指向原来的起始状态 ;
化简后结果 :
四、正则表达式转为非确定性有限自动机 NFA 示例 3
将正则表达式 ∅ ∗ \varnothing ^*∅
∗
转为 NFA ;
∅ ∗ \varnothing ^*∅
∗
= { ε } =\{ \varepsilon \}={ε}
构造原子自动机 : 注意从 非接受状态 → \to→ 接受状态 ;
