没有合适的资源?快使用搜索试试~ 我知道了~
首页NFA的确定化(NFA->DFA)(完整可运行代码)
NFA的确定化(NFA->DFA)(完整可运行代码)
4星 · 超过85%的资源 需积分: 49 79 下载量 14 浏览量
更新于2023-05-22
评论 4
收藏 112KB DOC 举报
本程序的目的数据结构是一个储存所有子集集合的一个结构体,包含子集中所有的状态,利用邻接表实现。 算法正如书上所说,子集构造算法如下: 假定所构造的子集族为C,即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。 (1)开始,令-closure(K0)为C中唯一成员,并且它是未被标记的。 (2)while (C中存在尚未被标记的子集T)do { 标记T; for 每个输入字母a do { U:= -closure(move(T,a)); if U不在C中 then 将U作为未标记的子集加在C中 } } 输入文本格式样例: A B C D E F G H I J K L M N O P Q R S T # A a B C * D E a F G d H M a N O d P Q * M Q * O N * R P * R I * E I * G F * J H * J K * I J * L J * I K * L B * S S * K S * C D * T R * T L * Q
资源详情
资源评论
资源推荐
编译原理实验报告
实验名称 NFA
的确定化( NFA->DFA )
实验时间 2017.4.13
院系 计算机科学与技术
班级 科技二班
学号
姓名
1.实验目的
输入: 非确定有限(穷)状态自动机。
输出: 确定化的有限(穷)状态自动机
2.实验原理
一 个 确 定 的 有 限 自 动 机 ( ) 可 以 定 义 为 一 个 五 元 组 , =
(,∑,,,),其中:
是一个有穷非空集,集合中的每个元素称为一个状态;
是一个有穷字母表,∑中的每个元素称为一个输入符号;
是 一 个 从 的 单 值 转 换 函 数 , 即 ( , ) = ,
(,)表示当前状态为 ,如果输入字符 ,则转到状态 ,状态
称为状态 的后继状态;
,是惟一的初态;
,是一个终态集。
由定义可见,确定有限自动机只有惟一的一个初态,但可以有多个终态,
每个状态对字母表中的任一输入符号,最多只有一个后继状态。
对于 ,若存在一条从某个初态结点到某一个终态结点的通路,则称
这条通路上的所有弧的标记符连接形成的字符串可为 所接受。若 的
初态结点同时又是终态结点,则称 可为 所接受(或识别), 所能接
受的全部字符串(字)组成的集合记作 ()。
一 个 不 确 定有 限 自 动 机 ( ) 可 以 定 义 为 一 个 五 元 组 , =
(,∑,,,),其中:
是一个有穷非空集,集合中的每个元素称为一个状态;
是一个有穷字母表,∑中的每个元素称为一个输入符号;
是一个从 的子集的转换函数;
,是一个非空的初态集;
,是一个终态集。
由定义可见,不确定有限自动机 与确定有限自动机 的主要区别
是
() 的初始状态 为一个状态集,即允许有多个初始状态;
() 中允许状态在某输出边上有相同的符号,即对同一个输入符号
可以有多个后继状态。即 中的 是单值函数,而 中的 是多值函数。
因此,可以将确定有限自动机 看作是不确定有限自动机 的特例。
和 一样, 也可以用矩阵和状态转换图来表示。
对于 ,若存在一条从某个初态结点到某一个终态结点的通路,则称
这条通路上的所有弧的标记( 除外)连接形成的字符串可为 所接受。
所能接受的全部字符串(字)组成的集合记作 ()。
由于 是 的特例,所以能被 所接受的符号串必能被 所接
受。
设
和
是同一个字母集∑上的有限自动机,若 (
)=(
),则
称有限自动机
和
等价。
由以上定义可知,若两个自动机能够接受相同的语言,则称这两个自动机
等价。 是 的特例,因此对于每一个
总存在一个
,使
得 (
)=(
)。即一个不确定有限自动机能接受的语言总可以找到一
个等价的确定有限自动机来接受该语言。
NFA 确定化为 DFA
同一个字符串 可以由多条通路产生,而在实际应用中,作为描述控制过
程的自动机,通常都是确定有限自动机 ,因此这就需要将不确定有限自动
机转换成等价的确定有限自动机,这个过程称为不确定有限自动机的确定化,
即 确定化为 。
下面介绍一种 的确定化算法,这种算法称为子集法:
若 的全部初态为
,
,…,
,则令 的初态为:
=
,
,…,
,其中方括号用来表示若干个状态构成的某一状态。
设 的状态集 中 有一状 态为
,
,… ,
, 若对 某符 号
,在 中有 (!
,
,…,
",)#!
$
,
$
,…,
$
"
则令 (!
,
,…,
",)#!
$
,
$
,…,
$
"为 的一个
转换函数。若
$
,
$
,…,
%
不在 中,则将其作为新的状态加入到 中。
重复第 步,直到 中不再有新的状态加入为止。
上面得到 的所有 状态 构成 的状态集 ,转换函数构 成 的
, 的字母表仍然是 的字母表∑。
中凡是含有 终态的状态都是 的终态。
对于上述 确定化算法——子集法,还可以采用另一种操作性更强的描
述方式,下面我们给出其详细描述。首先给出两个相关定义。
假 设 & 是 状 态 集 的 一 个 子 集 ( 即 & ) , 则 定 义 '
()*+,-.(&)为:
若 &,则 '()*+,-.(&);
若 &,则从 出发经过任 意条 弧而能到达的任何状态 $,则
$'()*+,-.(&)。
状态集 '()*+,-.(&)称为状态 & 的 闭包。
假设 =(,∑,,,),若 &,,则定义 &
='
()*+,-.(/),其中 / 是所有从 '()*+,-.(&)出发,经过一条 弧而到达的
状态集。
确定化的实质是以原有状态集上的子集作为 上的一个状态,将原
状态间的转换为该子集间的转换,从而把不确定有限自动机确定化。经过确定
化后,状态数可能增加,而且可能出现一些等价状态,这时就需要简化。
3..实验内容
本程序的目的数据结构是一个储存所有子集集合的一个结构体,包含子集
中所有的状态,利用邻接表实现。
算法正如书上所说,子集构造算法如下:
假定所构造的子集族为 0,即 0#1232332&43其中 232332& 为状
态 的子集。
()开始,令'()*+,-.154为 0 中唯一成员,并且它是未被标记的。
()67).(0 中存在尚未被标记的子集 2)8*
!
剩余12页未读,继续阅读
漫浸天空的雨色
- 粉丝: 1275
- 资源: 12
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论3