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