文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【计算理论】计算理论总结 ( 非确定性有限自动机 NFA 转为确定性有限自动机 DFA | 示例 ) ★★

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

作者头像
韩曙亮
发布于 2023-03-28 20:06:24
发布于 2023-03-28 20:06:24
8590
举报
文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、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

b b b

{ 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 } {∅}

a
b
\{1, 3 \}
\{1 , 3\}
\{2\}
\{2\}
\{2,3\}
\{3\}
\{2,3\}
\{1,2,3\}
\{3\}
\{3\}
\{1,3\}
\{\varnothing \}
\{1,2,3\}
\{1,2,3\}
\{2,3\}
\{\varnothing \}
\{\varnothing \}
\{\varnothing \}

凡是 包含 NFA 中接受状态

1

的新状态 都是 接受状态 ;

\{1, 3 \}

和

\{1, 2, 3 \}

都是接受状态 , 画图时都是 双圈 ;

空集

\{\varnothing \}

状态 , 接受任何字符都是空集

\{\varnothing \}

;

最终的 DFA 如下 :

详细推理过程 : 【计算理论】非确定性有限自动机 ( NFA ) 转换成 确定性有限自动机 ( DFA )

二、NFA 转 DFA 示例 2

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

NFA 的状态集

\rm \{ 1,2,3 \}

, 字符集

\rm \{ a,b \}

;

从 起始状态

1

开始分析 , 读取

\rm \varepsilon

无条件跳转到

2

, 这里形成了新的状态

\rm \{1, 2\}

, 写到下面表格中 ;

\rm \{1, 2\}

状态 下读取

\rm a

字符结果是

\rm \{1, 2,3\}

, 读取

\rm b

字符结果是

\{\varnothing \}

;

\rm \{1, 2, 3\}

状态 下读取

\rm a

字符结果是

\rm \{1, 2,3\}

, 读取

\rm b

字符结果是

\{2, 3\}

;

\rm \{ 2, 3\}

状态 下读取

\rm a

字符结果是

\rm \{1, 2\}

, 读取

\rm b

字符结果是

\{2, 3\}

;

​

a a a

b b b

{ 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 } {∅}

a
b
\{1, 2 \}
\{1 , 2, 3\}
\{ \varnothing \}
\{1 , 2, 3\}
\{2,3\}
\{2,3\}
\{2,3\}
\{1,2\}
\{2,3\}
\{\varnothing \}
\{\varnothing \}
\{\varnothing \}

凡是 包含 NFA 中接受状态

2

的新状态 都是 接受状态 ;

\{1, 2 \}

,

\{2, 3 \}

和

\{1, 2, 3 \}

都是接受状态 , 画图时都是 双圈 ;

空集

\{\varnothing \}

状态 , 接受任何字符都是空集

\{\varnothing \}

;

最终的 DFA 如下 :

三、NFA 转 DFA 示例 3

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

NFA 的状态集

\rm \{ 1,2 \}

, 字符集

\rm \{ a,b \}

;

从 起始状态

1

开始分析 ,

\rm \{1\}

状态 下读取

\rm a

字符结果是

\rm \{1, 2\}

, 读取

\rm b

字符结果是

\{ 2 \}

;

\rm \{1, 2\}

状态 下读取

\rm a

字符结果是

\rm \{1, 2\}

, 读取

\rm b

字符结果是

\{1, 2 \}

;

\rm \{2\}

状态 下读取

\rm a

字符结果是

\{ \varnothing \}

, 读取

\rm b

字符结果是

\{1\}

;

​

a a a

b b b

{ 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 } {∅}

a
b
\{1 \}
\{1 , 2\}
\{ 2 \}
\{1 , 2\}
\{1, 2\}
\{1,2\}
\{2\}
\{ \varnothing \}
\{1\}
\{\varnothing \}
\{\varnothing \}
\{\varnothing \}

凡是 包含 NFA 中接受状态

1

的新状态 都是 接受状态 ;

\{1\}

和

\{1, 2 \}

都是接受状态 , 画图时都是 双圈 ;

空集

\{\varnothing \}

状态 , 接受任何字符都是空集

\{\varnothing \}

;

最终的 DFA 如下 :

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除
表格

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

表格
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 文章目录
  • 一、NFA 转 DFA 示例 1
  • 二、NFA 转 DFA 示例 2
  • 三、NFA 转 DFA 示例 3
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论