文章目录
一、NFA 转 DFA 示例 1
二、NFA 转 DFA 示例 2
三、NFA 转 DFA 示例 3
一、NFA 转 DFA 示例 1
将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ;
NFA 的状态集 { 1 , 2 , 3 } \rm \{ 1,2,3 \}{1,2,3} , 字符集 { a , b } \rm \{ a,b \}{a,b} ;
从 起始状态 1 11 开始分析 , 读取 ε \rm \varepsilonε 无条件跳转到 3 33 , 这里形成了新的状态 { 1 , 3 } \rm \{1, 3\}{1,3} , 写到下面表格中 ;
{ 1 , 3 } \rm \{1, 3\}{1,3} 状态 下读取 a \rm aa 字符结果是 { 1 , 3 } \rm \{1, 3\}{1,3} , 读取 b \rm bb 字符结果是 { 2 } \{2\}{2} , 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;
{ 2 } \{2\}{2} 状态下读取读取 a \rm aa 字符结果是 { 2 , 3 } \{2,3\}{2,3} , 读取 b \rm bb 字符结果是 { 3 } \{3\}{3} , 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;
{ 2 , 3 } \{2,3\}{2,3} 状态下读取读取 a \rm aa 字符结果是 { 1 , 2 , 3 } \{1, 2,3\}{1,2,3} , 读取 b \rm bb 字符结果是 { 3 } \{3\}{3} , 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;
{ 3 } \{3\}{3} 状态下读取读取 a \rm aa 字符结果是 { 1 , 3 } \{1,3\}{1,3} , 读取 b \rm bb 字符结果是 { ∅ } \{ \varnothing \}{∅} , 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;
{ 1 , 2 , 3 } \{1, 2,3\}{1,2,3} 状态下读取读取 a \rm aa 字符结果是 { 1 , 2 , 3 } \{1, 2,3\}{1,2,3} , 读取 b \rm bb 字符结果是 { 2 , 3 } \{2, 3\}{2,3} , 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;
{ ∅ } \{ \varnothing \}{∅} 状态下读取读取 a \rm aa 字符结果是 { ∅ } \{ \varnothing \}{∅} , 读取 b \rm bb 字符结果是 { ∅ } \{ \varnothing \}{∅} , 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ;
a aa b bb
{ 1 , 3 } \{1, 3 \}{1,3} { 1 , 3 } \{1 , 3\}{1,3} { 2 } \{2\}{2}
{ 2 } \{2\}{2} { 2 , 3 } \{2,3\}{2,3} { 3 } \{3\}{3}
{ 2 , 3 } \{2,3\}{2,3} { 1 , 2 , 3 } \{1,2,3\}{1,2,3} { 3 } \{3\}{3}
{ 3 } \{3\}{3} { 1 , 3 } \{1,3\}{1,3} { ∅ } \{\varnothing \}{∅}
{ 1 , 2 , 3 } \{1,2,3\}{1,2,3} { 1 , 2 , 3 } \{1,2,3\}{1,2,3} { 2 , 3 } \{2,3\}{2,3}
{ ∅ } \{\varnothing \}{∅} { ∅ } \{\varnothing \}{∅} { ∅ } \{\varnothing \}{∅}
凡是 包含 NFA 中接受状态 1 11 的新状态 都是 接受状态 ;
{ 1 , 3 } \{1, 3 \}{1,3} 和 { 1 , 2 , 3 } \{1, 2, 3 \}{1,2,3} 都是接受状态 , 画图时都是 双圈 ;
空集 { ∅ } \{\varnothing \}{∅} 状态 , 接受任何字符都是空集 { ∅ } \{\varnothing \}{∅} ;
最终的 DFA 如下 :
详细推理过程 : 【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA )
二、NFA 转 DFA 示例 2
将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ;
NFA 的状态集 { 1 , 2 , 3 } \rm \{ 1,2,3 \}{1,2,3} , 字符集 { a , b } \rm \{ a,b \}{a,b} ;
从 起始状态 1 11 开始分析 , 读取 ε \rm \varepsilonε 无条件跳转到 2 22 , 这里形成了新的状态 { 1 , 2 } \rm \{1, 2\}{1,2} , 写到下面表格中 ;
{ 1 , 2 } \rm \{1, 2\}{1,2} 状态 下读取 a \rm aa 字符结果是 { 1 , 2 , 3 } \rm \{1, 2,3\}{1,2,3} , 读取 b \rm bb 字符结果是 { ∅ } \{\varnothing \}{∅} ;
{ 1 , 2 , 3 } \rm \{1, 2, 3\}{1,2,3} 状态 下读取 a \rm aa 字符结果是 { 1 , 2 , 3 } \rm \{1, 2,3\}{1,2,3} , 读取 b \rm bb 字符结果是 { 2 , 3 } \{2, 3\}{2,3};
{ 2 , 3 } \rm \{ 2, 3\}{2,3} 状态 下读取 a \rm aa 字符结果是 { 1 , 2 } \rm \{1, 2\}{1,2} , 读取 b \rm bb 字符结果是 { 2 , 3 } \{2, 3\}{2,3};
a aa b bb
{ 1 , 2 } \{1, 2 \}{1,2} { 1 , 2 , 3 } \{1 , 2, 3\}{1,2,3} { ∅ } \{ \varnothing \}{∅}
{ 1 , 2 , 3 } \{1 , 2, 3\}{1,2,3} { 2 , 3 } \{2,3\}{2,3} { 2 , 3 } \{2,3\}{2,3}
{ 2 , 3 } \{2,3\}{2,3} { 1 , 2 } \{1,2\}{1,2} { 2 , 3 } \{2,3\}{2,3}
{ ∅ } \{\varnothing \}{∅} { ∅ } \{\varnothing \}{∅} { ∅ } \{\varnothing \}{∅}
凡是 包含 NFA 中接受状态 2 22 的新状态 都是 接受状态 ;
{ 1 , 2 } \{1, 2 \}{1,2} , { 2 , 3 } \{2, 3 \}{2,3} 和 { 1 , 2 , 3 } \{1, 2, 3 \}{1,2,3} 都是接受状态 , 画图时都是 双圈 ;
空集 { ∅ } \{\varnothing \}{∅} 状态 , 接受任何字符都是空集 { ∅ } \{\varnothing \}{∅} ;
最终的 DFA 如下 :
三、NFA 转 DFA 示例 3
将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ;
NFA 的状态集 { 1 , 2 } \rm \{ 1,2 \}{1,2} , 字符集 { a , b } \rm \{ a,b \}{a,b} ;
从 起始状态 1 11 开始分析 ,
{ 1 } \rm \{1\}{1} 状态 下读取 a \rm aa 字符结果是 { 1 , 2 } \rm \{1, 2\}{1,2} , 读取 b \rm bb 字符结果是 { 2 } \{ 2 \}{2} ;
{ 1 , 2 } \rm \{1, 2\}{1,2} 状态 下读取 a \rm aa 字符结果是 { 1 , 2 } \rm \{1, 2\}{1,2} , 读取 b \rm bb 字符结果是 { 1 , 2 } \{1, 2 \}{1,2} ;
{ 2 } \rm \{2\}{2} 状态 下读取 a \rm aa 字符结果是 { ∅ } \{ \varnothing \}{∅} , 读取 b \rm bb 字符结果是 { 1 } \{1\}{1};
a aa b bb
{ 1 } \{1 \}{1} { 1 , 2 } \{1 , 2\}{1,2} { 2 } \{ 2 \}{2}
{ 1 , 2 } \{1 , 2\}{1,2} { 1 , 2 } \{1, 2\}{1,2} { 1 , 2 } \{1,2\}{1,2}
{ 2 } \{2\}{2} { ∅ } \{ \varnothing \}{∅} { 1 } \{1\}{1}
{ ∅ } \{\varnothing \}{∅} { ∅ } \{\varnothing \}{∅} { ∅ } \{\varnothing \}{∅}
凡是 包含 NFA 中接受状态 1 11 的新状态 都是 接受状态 ;
{ 1 } \{1\}{1} 和 { 1 , 2 } \{1, 2 \}{1,2} 都是接受状态 , 画图时都是 双圈 ;
空集 { ∅ } \{\varnothing \}{∅} 状态 , 接受任何字符都是空集 { ∅ } \{\varnothing \}{∅} ;
最终的 DFA 如下 :
