【计算理论】计算理论总结 ( 非确定性有限自动机 NFA 转为确定性有限自动机 DFA | 示例 ) ★★

发布于

文章目录

  • 一、NFA 转 DFA 示例 1
  • 二、NFA 转 DFA 示例 2
  • 三、NFA 转 DFA 示例 3

一、NFA 转 DFA 示例 1

将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ;

NFA 的状态集

\rm \{ 1,2,3 \}

, 字符集

\rm \{ a,b \}

;

从 起始状态

1

开始分析 , 读取

\rm \varepsilon

无条件跳转到

3

, 这里形成了新的状态

\rm \{1, 3\}

, 写到下面表格中 ;

\rm \{1, 3\}

状态 下读取

\rm a

字符结果是

\rm \{1, 3\}

, 读取

\rm b

字符结果是

\{2\}

, 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;

\{2\}

状态下读取读取

\rm a

字符结果是

\{2,3\}

, 读取

\rm b

字符结果是

\{3\}

, 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;

\{2,3\}

状态下读取读取

\rm a

字符结果是

\{1, 2,3\}

, 读取

\rm b

字符结果是

\{3\}

, 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;

\{3\}

状态下读取读取

\rm a

字符结果是

\{1,3\}

, 读取

\rm b

字符结果是

\{ \varnothing \}

, 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;

\{1, 2,3\}

状态下读取读取

\rm a

字符结果是

\{1, 2,3\}

, 读取

\rm b

字符结果是

\{2, 3\}

, 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ; 将新状态写到表格中 , 然后分析新状态 ;

\{ \varnothing \}

状态下读取读取

\rm a

字符结果是

\{ \varnothing \}

, 读取

\rm b

字符结果是

\{ \varnothing \}

, 上述分别是 NFA 下两个状态读取字符的后继状态取并集 ;

​

a 

      a
     
    
   a</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>b
      
     
     
      b
     
    
   b</p></div></div></th></tr></thead><tbody><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {1, 3 }
     
    
   {1,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {1 , 3}
     
    
   {1,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       }
      
     
     
      {2}
     
    
   {2}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       }
      
     
     
      {2}
     
    
   {2}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {2,3}
     
    
   {2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       3
      
      
       }
      
     
     
      {3}
     
    
   {3}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {2,3}
     
    
   {2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {1,2,3}
     
    
   {1,2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       3
      
      
       }
      
     
     
      {3}
     
    
   {3}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       3
      
      
       }
      
     
     
      {3}
     
    
   {3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {1,3}
     
    
   {1,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {1,2,3}
     
    
   {1,2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {1,2,3}
     
    
   {1,2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {2,3}
     
    
   {2,3}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td></tr></tbody></table></div><figure class=""><span>a</span></figure><figure class=""><span>b</span></figure><figure class=""><span>\{1, 3 \}</span></figure><figure class=""><span>\{1 , 3\}</span></figure><figure class=""><span>\{2\}</span></figure><figure class=""><span>\{2\}</span></figure><figure class=""><span>\{2,3\}</span></figure><figure class=""><span>\{3\}</span></figure><figure class=""><span>\{2,3\}</span></figure><figure class=""><span>\{1,2,3\}</span></figure><figure class=""><span>\{3\}</span></figure><figure class=""><span>\{3\}</span></figure><figure class=""><span>\{1,3\}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><figure class=""><span>\{1,2,3\}</span></figure><figure class=""><span>\{1,2,3\}</span></figure><figure class=""><span>\{2,3\}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><p>凡是 包含 NFA 中接受状态 </p><figure class=""><span>1</span></figure><p> 的新状态 都是 接受状态 ;</p><figure class=""><span>\{1, 3 \}</span></figure><p> 和 </p><figure class=""><span>\{1, 2, 3 \}</span></figure><p> 都是接受状态 , 画图时都是 双圈 ;</p><p>空集 </p><figure class=""><span>\{\varnothing \}</span></figure><p> 状态 , 接受任何字符都是空集 </p><figure class=""><span>\{\varnothing \}</span></figure><p> ;</p><p><strong>最终的 DFA 如下 :</strong></p><figure class=""><div class="rno-markdown-img-url" style="text-align:center"><div class="rno-markdown-img-url-inner" style="width:71.56%"><div style="width:100%"><img src="https://cdn.static.attains.cn/app/developer-bbs/upload/1723291211112776479.png" /></div></div></div></figure><p><strong>详细推理过程 :</strong> 【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA )</p><h2 id="11751" name="%E4%BA%8C%E3%80%81NFA-%E8%BD%AC-DFA-%E7%A4%BA%E4%BE%8B-2">二、NFA 转 DFA 示例 2</h2><figure class=""><hr/></figure><p><strong>将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ;</strong></p><figure class=""><div class="rno-markdown-img-url" style="text-align:center"><div class="rno-markdown-img-url-inner" style="width:47.2%"><div style="width:100%"><img src="https://cdn.static.attains.cn/app/developer-bbs/upload/1723291211365710516.png" /></div></div></div></figure><p><strong>NFA 的状态集</strong> </p><figure class=""><span>\rm \{ 1,2,3 \}</span></figure><p> <strong>, 字符集</strong> </p><figure class=""><span>\rm \{ a,b \}</span></figure><p> <strong>;</strong></p><p>从 起始状态 </p><figure class=""><span>1</span></figure><p> 开始分析 , 读取 </p><figure class=""><span>\rm \varepsilon</span></figure><p> 无条件跳转到 </p><figure class=""><span>2</span></figure><p> , 这里形成了新的状态 </p><figure class=""><span>\rm \{1, 2\}</span></figure><p> , 写到下面表格中 ;</p><figure class=""><span>\rm \{1, 2\}</span></figure><p> 状态 下读取 </p><figure class=""><span>\rm a</span></figure><p> 字符结果是 </p><figure class=""><span>\rm \{1, 2,3\}</span></figure><p> , 读取 </p><figure class=""><span>\rm b</span></figure><p> 字符结果是 </p><figure class=""><span>\{\varnothing \}</span></figure><p> ;</p><figure class=""><span>\rm \{1, 2, 3\}</span></figure><p> 状态 下读取 </p><figure class=""><span>\rm a</span></figure><p> 字符结果是 </p><figure class=""><span>\rm \{1, 2,3\}</span></figure><p> , 读取 </p><figure class=""><span>\rm b</span></figure><p> 字符结果是 </p><figure class=""><span>\{2, 3\}</span></figure><p>;</p><figure class=""><span>\rm \{ 2, 3\}</span></figure><p> 状态 下读取 </p><figure class=""><span>\rm a</span></figure><p> 字符结果是 </p><figure class=""><span>\rm \{1, 2\}</span></figure><p> , 读取 </p><figure class=""><span>\rm b</span></figure><p> 字符结果是 </p><figure class=""><span>\{2, 3\}</span></figure><p>;</p><div class="table-wrapper"><table><thead><tr><th style="text-align:left"><div><div class="table-header"><p>​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>a
      
     
     
      a
     
    
   a</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>b
      
     
     
      b
     
    
   b</p></div></div></th></tr></thead><tbody><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       }
      
     
     
      {1, 2 }
     
    
   {1,2}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {1 , 2, 3}
     
    
   {1,2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      { \varnothing }
     
    
   {∅}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {1 , 2, 3}
     
    
   {1,2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {2,3}
     
    
   {2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {2,3}
     
    
   {2,3}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {2,3}
     
    
   {2,3}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       }
      
     
     
      {1,2}
     
    
   {1,2}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       ,
      
      
       3
      
      
       }
      
     
     
      {2,3}
     
    
   {2,3}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td></tr></tbody></table></div><figure class=""><span>a</span></figure><figure class=""><span>b</span></figure><figure class=""><span>\{1, 2 \}</span></figure><figure class=""><span>\{1 , 2, 3\}</span></figure><figure class=""><span>\{ \varnothing \}</span></figure><figure class=""><span>\{1 , 2, 3\}</span></figure><figure class=""><span>\{2,3\}</span></figure><figure class=""><span>\{2,3\}</span></figure><figure class=""><span>\{2,3\}</span></figure><figure class=""><span>\{1,2\}</span></figure><figure class=""><span>\{2,3\}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><p>凡是 包含 NFA 中接受状态 </p><figure class=""><span>2</span></figure><p> 的新状态 都是 接受状态 ;</p><figure class=""><span>\{1, 2 \}</span></figure><p> , </p><figure class=""><span>\{2, 3 \}</span></figure><p> 和 </p><figure class=""><span>\{1, 2, 3 \}</span></figure><p> 都是接受状态 , 画图时都是 双圈 ;</p><p>空集 </p><figure class=""><span>\{\varnothing \}</span></figure><p> 状态 , 接受任何字符都是空集 </p><figure class=""><span>\{\varnothing \}</span></figure><p> ;</p><p><strong>最终的 DFA 如下 :</strong></p><figure class=""><div class="rno-markdown-img-url" style="text-align:center"><div class="rno-markdown-img-url-inner" style="width:49.49%"><div style="width:100%"><img src="https://cdn.static.attains.cn/app/developer-bbs/upload/1723291211683471003.png" /></div></div></div></figure><h2 id="11868" name="%E4%B8%89%E3%80%81NFA-%E8%BD%AC-DFA-%E7%A4%BA%E4%BE%8B-3">三、NFA 转 DFA 示例 3</h2><figure class=""><hr/></figure><p><strong>将下图的 非确定性有限自动机 NFA 转为确定性有限自动机 DFA ;</strong></p><figure class=""><div class="rno-markdown-img-url" style="text-align:center"><div class="rno-markdown-img-url-inner" style="width:42.22%"><div style="width:100%"><img src="https://cdn.static.attains.cn/app/developer-bbs/upload/1723291212005613542.png" /></div></div></div></figure><p><strong>NFA 的状态集</strong> </p><figure class=""><span>\rm \{ 1,2 \}</span></figure><p> <strong>, 字符集</strong> </p><figure class=""><span>\rm \{ a,b \}</span></figure><p> <strong>;</strong></p><p>从 起始状态 </p><figure class=""><span>1</span></figure><p> 开始分析 ,</p><figure class=""><span>\rm \{1\}</span></figure><p> 状态 下读取 </p><figure class=""><span>\rm a</span></figure><p> 字符结果是 </p><figure class=""><span>\rm \{1, 2\}</span></figure><p> , 读取 </p><figure class=""><span>\rm b</span></figure><p> 字符结果是 </p><figure class=""><span>\{ 2 \}</span></figure><p> ;</p><figure class=""><span>\rm \{1, 2\}</span></figure><p> 状态 下读取 </p><figure class=""><span>\rm a</span></figure><p> 字符结果是 </p><figure class=""><span>\rm \{1, 2\}</span></figure><p> , 读取 </p><figure class=""><span>\rm b</span></figure><p> 字符结果是 </p><figure class=""><span>\{1, 2 \}</span></figure><p> ;</p><figure class=""><span>\rm \{2\}</span></figure><p> 状态 下读取 </p><figure class=""><span>\rm a</span></figure><p> 字符结果是 </p><figure class=""><span>\{ \varnothing \}</span></figure><p> , 读取 </p><figure class=""><span>\rm b</span></figure><p> 字符结果是 </p><figure class=""><span>\{1\}</span></figure><p>;</p><div class="table-wrapper"><table><thead><tr><th style="text-align:left"><div><div class="table-header"><p>​</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>a
      
     
     
      a
     
    
   a</p></div></div></th><th style="text-align:left"><div><div class="table-header"><p>b
      
     
     
      b
     
    
   b</p></div></div></th></tr></thead><tbody><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       }
      
     
     
      {1 }
     
    
   {1}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       }
      
     
     
      {1 , 2}
     
    
   {1,2}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       }
      
     
     
      { 2 }
     
    
   {2}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       }
      
     
     
      {1 , 2}
     
    
   {1,2}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       }
      
     
     
      {1, 2}
     
    
   {1,2}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       ,
      
      
       2
      
      
       }
      
     
     
      {1,2}
     
    
   {1,2}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       2
      
      
       }
      
     
     
      {2}
     
    
   {2}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      { \varnothing }
     
    
   {∅}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       1
      
      
       }
      
     
     
      {1}
     
    
   {1}</p></div></div></td></tr><tr><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td><td style="text-align:left"><div><div class="table-cell"><p>{
      
      
       ∅
      
      
       }
      
     
     
      {\varnothing }
     
    
   {∅}</p></div></div></td></tr></tbody></table></div><figure class=""><span>a</span></figure><figure class=""><span>b</span></figure><figure class=""><span>\{1 \}</span></figure><figure class=""><span>\{1 , 2\}</span></figure><figure class=""><span>\{ 2 \}</span></figure><figure class=""><span>\{1 , 2\}</span></figure><figure class=""><span>\{1, 2\}</span></figure><figure class=""><span>\{1,2\}</span></figure><figure class=""><span>\{2\}</span></figure><figure class=""><span>\{ \varnothing \}</span></figure><figure class=""><span>\{1\}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><figure class=""><span>\{\varnothing \}</span></figure><p>凡是 包含 NFA 中接受状态 </p><figure class=""><span>1</span></figure><p> 的新状态 都是 接受状态 ;</p><figure class=""><span>\{1\}</span></figure><p> 和 </p><figure class=""><span>\{1, 2 \}</span></figure><p> 都是接受状态 , 画图时都是 双圈 ;</p><p>空集 </p><figure class=""><span>\{\varnothing \}</span></figure><p> 状态 , 接受任何字符都是空集 </p><figure class=""><span>\{\varnothing \}</span></figure><p> ;</p><p><strong>最终的 DFA 如下 :</strong></p><figure class=""><div class="rno-markdown-img-url" style="text-align:center"><div class="rno-markdown-img-url-inner" style="width:51.79%"><div style="width:100%"><img src="https://cdn.static.attains.cn/app/developer-bbs/upload/1723291212366483240.png" /></div></div></div></figure>
#表格