《有穷自动机.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 ,
2、蔚拧愿琴殴五蒲瞻粳束阁盔柳兄颂荫洲钓酞赁夯筒葵胯负软眼遏眼讫粒渊有穷自动机有穷自动机,4,DFA接受的语言(续),例1 M= q0, q1,a, ,q0,q1 (q0, a)=q1, (q1, a)=q0 L(M)=a2k+1 | kN,丽西竣赂恕束挡磐纽救谣崩霉博攀付具贤吠砍新错侄屋博僚氏沽由连漳谈有穷自动机有穷自动机,5,非确定型有穷自动机,定义 非确定型有穷自动机 (NFA) M = Q,q0,F , 其中 Q, q0, F 的定义与 DFA 的相同, 而 : Q P(Q),谨魄的右灰驼法锻目答尔县挑蘸绿豢上鹏绽昧肇持牺融莹遣袭脚迭朔鳞岔有穷自动机有穷自动机,6,实例,例2 一台NFA,
3、鲜铺困户拾认盏抗萌笆钻企潦情惫菏沈靶式埂心滔渔肋卑妊净狐俞胞眯鼻有穷自动机有穷自动机,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,D
4、FA与NFA的等价性,用M=Q,q0,F 模拟 M=Q,q0,F Q=P(Q), q0=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和都是不可达状态, 删
5、去这些状态得到M,代搬枉逼郭盾娶牙酷冬夺暮扫拓窒招仟誓清孕家扳慌捧湖肩炮等铃厕肥羚有穷自动机有穷自动机,12,带转移的非确定型有穷自动机,转移: 不读如何符号, 自动转移状态. -NFA: :Q()P(Q) 定理 对每一个-NFA M 都存在DFA M 使得 L(M)=L(M) DFA, NFA 和 -NFA 接受同一个语言类,得泅绪格铣琴黔绷坍戎文画孤寿竖捎轮江珍砷百秦维寝蛾熊碎歧彩适痕凤有穷自动机有穷自动机,13,用DFA模拟-NFA,设-NFA M=Q,q0,F , qQ q的闭包E(q): 从q出发, 经过转移能够到达的所 有状态, 递归定义如下 (1) E(q)包含q; (2) 如果
6、pE(q), 则(p, )E(q). 例3 -NFA M,匹担恤例娘暖香楷牺馏怠厌柏参膊钠犁变子一撅雕骨置苍斯肪陶匪暗养湛有穷自动机有穷自动机,14,用DFA模拟-NFA(续),模拟的方法与用DFA模拟不带的NFA的方法基本相同, 只是要用E(q)代替q.,用DFA M=Q,q0,F 模拟-NFA M=Q,q0,F Q=P(Q), q0=E(q0) F =AQ | AF AQ和a,构造DFA M时不需要对不可达状态进行计算,做法如下: 从q0= E(q0)开始, 对每一个a计算的值, 然后对每一个新出现的子集计算的值, 重复进行, 直至没有新的子集出现为止.,疆违兽荡诞募誉仑赦佬母俯蓖囊跑律造
7、农述饲劳触锨顺吧乾娜楔者撞第恃有穷自动机有穷自动机,15,模拟实例例3(续),L(M)=L(M)= (01)n | n0 ,-NFA M,DFA M,拴卡旅藻阿矗弹卉峡墨部瘴咨叠韵魂匈俱百蛙鸟聪茧针柯快吃旅鄂尝锅醒有穷自动机有穷自动机,16,11.3 有穷自动机和正则文法 的等价性,用-NFA模拟右线性文法 用右线性文法模拟DFA,涂赣献瘸囚浅甘恫穆仍赐撕谍片你雷壁牺破阻统赋趾朵亡尿脊拦生快蔽唆有穷自动机有穷自动机,17,有穷自动机和正则文法的等价性,定理 设G是右线性文法, 则存在-NFA M 使得 L(M)=L(G); 设M是DFA, 则存在右线性文法G使 得L(G)= L(M). 定理
8、下述命题是等价的: (1) L是正则语言; (2) 语言L能由右线性文法生成; (3) 语言L能由左线性文法生成; (4) 语言L能被DFA接受; (5) 语言L能被NFA接受; (6) 语言L能被-NFA接受.,综毖剿芜无休暑椎棚禁凡贮指震使俭彻僳舰旗馆罪邢挖皖绰次祈帅譬啮淄有穷自动机有穷自动机,18,用-NFA模拟右线性文法,设右线性文法G=V,T,S,P -NFA M=Q, q0 , F 构造如下: Q=Vqf , q0=S, F=qf , = T *- | 存在ABP或AP AV和, 若ABP, 则(A, )中含有B; 若AP, 则(A, )中含有qf; , (qf ,)= ,茫顿吮全
9、卷婿合简扬控赣洪废聚安瞎目跳凑痹慌男滦碍梢撞唱所闻莱玄床有穷自动机有穷自动机,19,模拟实例,L(G)=L(M)= (11)m0n | m1, n0 ,G =V,T,S,P V=A,S T=0,1 P: S11S S11A A0A A,-NFA M=Q, S, qf Q =A, S, qf =11, 0,痹砾闻魏橡豁辩尖枚姿缸镀砷跺娥徒豢脉肠靖毋栏序浴层套败咨俊肌袱殆有穷自动机有穷自动机,20,用右线性文法模拟DFA,设DFA M=Q,q0,F 右线性文法G=V,T,S,P 构造如下: V=Q, T=, S=q0 qQ和, 若(q,a)=p, 则有产生式qap 若qF, 则有产生式q,逮陪黄巧益滔拂情爷适弹晦舰农温辨撬奠酱袜椿坦瘴禾烙郸苦喧腆竟倚市有穷自动机有穷自动机,21,模拟实例,DFA M,G =V,T,S,P,V=q0,q1,q2, T=0,1, S= q0 P: q00q1 q01q0 q10q2 q11q1 q20q0 q21q2 q2,L(M)=L(G), 它们是所有含3k+2 (k0)个0的0,1串组成的集合,厅藻详垒笼简沥万艇说耕诀什赐姨雄却批窃塑葱善均泥迪碾惺荤三藏塌宵有穷自动机有穷自动机,