有穷自动机.ppt
《有穷自动机.ppt》由会员分享,可在线阅读,更多相关《有穷自动机.ppt(21页珍藏版)》请在三一文库上搜索。
1、1,11.2 有穷自动机,确定型有穷自动机(DFA) 非确定型有穷自动机(NFA) 带转移的NFA(-NFA),2,确定型有穷自动机,3,DFA接受的语言,把扩张到Q*上 *:Q*Q, 递归定义如下 qQ, a和w* *(q,)=q *(q,wa)= (*(q,w),a) 定义 w*,如果*(q0,w)F, 则称 M接受w. M接受的字符串的全体称作M接受的语言,记作 L(M), 即 L(M)= w*| *(q0,w)F ,4,DFA接受的语言(续),例1 M= q0, q1,a, ,q0,q1 (q0, a)=q1, (q1, a)=q0 L(M)=a2k+1 | kN,5,非确定型有穷自动
2、机,定义 非确定型有穷自动机 (NFA) M = Q,q0,F , 其中 Q, q0, F 的定义与 DFA 的相同, 而 : Q P(Q),6,实例,例2 一台NFA,7,NFA接受的语言,*:Q*Q 递归定义如下: qQ, a 和 w* *(q,)=q *(q,wa)= 定义 w*,如果*(q0 ,w)F, 则称M接受w. M接受的字符串的全体称作M接受的语言,记作 L(M), 即 L(M)= w*| *(q0 ,w)F ,8,例2 (续),L(G) = x00y, x11y | x,y0,1*,9,DFA与NFA的等价性,用M=Q,q0,F 模拟 M=Q,q0,F Q=P(Q), q0=
3、q0 F= AQ | AF AQ 和 a,定理 对每一个NFA M 都存在DFA M 使得 L(M)=L(M ),10,模拟实例,NFA M,DFA M,11,模拟实例 (续),不可达状态:从初始状态出发永远不可能达到的状态 删去所有的不可达状态, 不会改变FA接受的语言. 如M中的q1,q2,q0,q2,q1,q2和都是不可达状态, 删去这些状态得到M,12,带转移的非确定型有穷自动机,转移: 不读如何符号, 自动转移状态. -NFA: :Q()P(Q) 定理 对每一个-NFA M 都存在DFA M 使得 L(M)=L(M) DFA, NFA 和 -NFA 接受同一个语言类,13,用DFA模
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 有穷 自动机
链接地址:https://www.31doc.com/p-3297288.html