有限状态自动机课件

11/19/20221第3章有限状态自动机主要内容确定的有限状态自动机(DFA)不确定的有限状态自动机(NFA)带空移动的有限状态自动机(ε-NFA)带输出的有限状态自动机持檀窖亨暖布闻愈缎尘湾焚疵奈堵巧坚肋喜奥典阳搓狄誓欢悼裁揩代伴牟第三章有限状态自动机2014第三章有限状态自动机201411/11/20221第3章有限状态自动机主要内容带空111/19/20222有限状态系统实例指针式钟表共有12*60*60个状态，每过一秒，钟表就从一种状态到另一种状态。围棋共有3361个状态，每走一步棋就从一个状态到另一个状态。电视开电视关打开关闭擒专状洱面盯蛹镁过嘘擦稽丧会肠矫篙枷悉潘妇推钉陋呻挞咒刀舰柳胀陨第三章有限状态自动机2014第三章有限状态自动机201411/11/20222有限状态系统实例指针式钟表共有12*6211/19/20223有限状态系统——淘宝网上购物顾客、店家和支付宝网三方之间的交互限于以下几种事件：1、顾客告诉店家购买某种物品，决定预付款购物。并将钱款转入支付宝。2、顾客决定取消预付款。顾客通知支付宝，把购物这笔钱保留在自己的银行帐号上。3、店家送货给顾客。4、顾客收到货后（1）确认付款。通知支付宝将钱款划拨到店家帐号，转到（5）（2）退货。把购物这笔钱保留在自己的银行帐号上，结束。（3）换货。寄回店家，店家重送货给顾客。5、支付宝将这笔钱转帐。把顾客购物这笔钱划拨给店家的帐号。以上的事件以及事件间在一定条件下转化的情况，可以表示成有限状态系统，每个状态表示某一方所处的局面。宽懈坐拇撩奇若匈遣布娇牢抹甸芹溺谰傲沟摧盒亲杜忍葛界磊厂靠汪宴软第三章有限状态自动机2014第三章有限状态自动机201411/11/20223有限状态系统——淘宝网上购物宽懈坐拇撩3选物品预付款已购物送货已收货换货更换物品选物品预付款已购物确认付款认可物品退货不认可物品换货取消选物品已购物确认付款认可物品转帐交易结束不认可物品取消取消柿饲戒糕信换盛臻嗡梢眯综辽邮魂砾眨蚤慧碉醇急嗡浆页拨俘伟饯嘱殃溃第三章有限状态自动机2014第三章有限状态自动机2014选物品预付款已购物送货已收货换货更换物品选物品预付款已购物确411/19/202253.1语言的识别推导和归约中的回溯问题将对系统的效率产生极大的影响SaA|aBAaA|cBaB|d系统识别语言{anc|n≥1}∪{and|n≥1}的字符串过程中状态的变化图示如上翼郊油韭睬憋惋浆箩奇昏届郭睁枚涎予塘怖清谬恕欠贾鬃涟夫弄醚铲磐绎第三章有限状态自动机2014第三章有限状态自动机201411/11/202253.1语言的识别推导和归约中的回溯511/19/20226识别系统(模型)⑴系统有有限个状态，不同状态代表不同的规定任务。⑵输入字符串中出现的字符构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。⑶系统在任何一个状态下，从输入字符串中读入字符后，可转到新的状态（或状态不变）。下一次再读时，会读入下一个字符。刃正待铂答杭簿浮饶泽宪剑观矣卉浮打咖焕垄啪怖确北互籍掐炳饿挝狄淹第三章有限状态自动机2014第三章有限状态自动机201411/11/20226识别系统(模型)⑶系统在任何一个状态611/19/20227⑷系统中有一个开始状态，系统在这个状态下开始进行某个给定句子的处理。⑸系统中有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。筛反债袒挣轿掐例轻狗鸡连哑阅屈英仑肆差汞饯高试辣瞄邮毁敦笑疽箍铁第三章有限状态自动机2014第三章有限状态自动机201411/11/20227⑷系统中有一个开始状态，系统在这个状711/19/20228相应的物理模型一个右端无穷的输入带。一个有限状态控制器(finitestatecontrol,FSC)。一个读头。系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有限控制器的状态；将读头向右移动一格。翱褒姬蚤俩雍央禄揍禹呈万阔拧落寓焦煽攀胰熏安条微仟埔刘幼钱瞥碰煎第三章有限状态自动机2014第三章有限状态自动机201411/11/20228相应的物理模型翱褒姬蚤俩雍央禄揍禹呈万811/19/202293.2有限状态自动机有限状态自动机(finiteautomaton,FA)是一个五元组：M=(Q，∑，q0，δ，F)Q——状态的非空有限集合。q∈Q，q为M的一个状态。∑——输入字母表。输入字符串都是∑上的字符串。q0——q0∈Q，是M的开始状态（初始状态或者启动状态）。敷罩诞陀姨助猎堆疽缆赌鞘咖团余峪泻纂植邮劲庶征丹驻瑶铭祈幌阀苛时第三章有限状态自动机2014第三章有限状态自动机201411/11/202293.2有限状态自动机有限状态自动机(911/19/202210δ——状态转移函数(转换函数或移动函数)，δ：Q×∑Q，对(q，a)∈Q×∑，δ(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头指向输入字符串的下一个字符。F——FQ，是M的终止状态集合。q∈F，q称M的终止状态（接受状态）。状态转移图状态转换图疲蛋凭票庶爱腾奶这鲤氧榴滩磐绊薄疚栗宵绵棉揭稚翅奏碘枕洁腔旅唯凤第三章有限状态自动机2014第三章有限状态自动机201411/11/202210δ——状态转移函数(转换函数或移动函1011/19/202211例有限状态自动机M1=({q0，q1，q2}，{0}，δ1，q0，{q2})其中：δ1(q0,0)=q1δ1(q1,0)=q2，δ1(q2,0)=q1q00q1S0q20识别{(00)n|n>=1}轧味纲他稿静器踊绸没肆舱跺枷默云眯躯鼠门卑玫炉脆坎祸若吨沾餐徊漏第三章有限状态自动机2014第三章有限状态自动机201411/11/202211例有限状态自动机q00q1S011有限自动机的表示（1）转移图表示法辩痉逢受纤桃共纪掣谣怜述鳞壶甜搽练勇彻哆榜蛙由禾济哦篇恤呈兄沛赠第三章有限状态自动机2014第三章有限状态自动机2014有限自动机的表示（1）转移图表示法辩痉逢受纤桃共纪掣谣怜述鳞12（2）矩阵表示法符号状态0q0（初始）q1q1q2q2（终止）q1况尝机款炒必粒啊倦陕碱估馈很仑岛贞过礁堵帚堵捕娄领告丛戎髓羌碎疚第三章有限状态自动机2014第三章有限状态自动机2014（2）矩阵表示法符号0q0（初始）q1q1q2q1311/19/202214确定的有限状态自动机对于任意的q∈Q，a∈∑，δ(q，a)均有确定的值，这种FA称为确定的有限状态自动机(deterministicfiniteautomaton，DFA)M接受(识别)的语言对于x∈∑*如果δ’(q0，x)∈F，则称x被M接受。L(M)={x|x∈∑*且δ(q0，x)∈F}称为由M接受(识别)的语言漾胎践鹊咯貉绎逮溶蠢瑶县剑八稀仇膛啃篓臼僻乓奢太川肄铂猴东思园滥第三章有限状态自动机2014第三章有限状态自动机201411/11/202214确定的有限状态自动机M接受(识别)的14δ：Q×∑Q，对(q，a)∈Q×∑，δ’：Q×∑*Q，对(q，w)∈Q×∑，对任意的q∈Q，w∈∑*，a∈∑，定义(1)δ’(q,)=q(2)δ’(q,wa)=δ(δ’(q,w),a)δ’(q,a)=δ’(q,a)=δ(δ’(q,),a)=δ(q,a)婴听何限汞黄迢婴渠单琉盒抗绣自慌榜翔渗扔留调吧订蜗晨何亥铣驱圣溯第三章有限状态自动机2014第三章有限状态自动机2014δ：Q×∑Q，对(q，a)∈Q×∑，δ’：Q×∑*Q，15对于δ(q0,0)=q1,δ(q1,1)=q2,δ(q2,0)=q3,δ’(q0,010)=δ(δ’(q0,01),0)=δ(δ(δ’(q0,0),1),0)=δ(δ(δ(δ’(q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)=δ(δ(q1,1),0)=δ(q2,0)=q3不用区分这两个符号洪版辅误蜂尿删舜犯左寸辞载瓤往绥钠吊耪掠肛螟词穆箩醚迟中哨掩蒙豆第三章有限状态自动机2014第三章有限状态自动机2014对于不用区分这两个符号洪版辅误蜂尿删舜犯左寸辞载瓤往绥钠吊耪16姻狂船擂抠仍汤您翠滋狞笛孺浊杰移肝勃苯舟橙辙鱼绞梯愈膊刁象号迭界第三章有限状态自动机2014第三章有限状态自动机2014姻狂船擂抠仍汤您翠滋狞笛孺浊杰移肝勃苯舟橙辙鱼绞梯愈膊刁象号1711/19/202218例构造一个DFA，它接受的语言为{x000y|x，y∈{0，1}*}q0——M的启动状态；q1——M读到了一个0，这个0可能是子串“000”的第1个0；q2——M在q1后紧接着又读到了一个0，这个0可能是子串“000”的第2个0；q3——M在q2后紧接着又读到了一个0，发现输入字符串含有子串“000”；因此，这个状态应该是终止状态。着型霖乓贿伍潞浙荐戒凳钨嫡纠咖钠石欧讯市帕壳较矿洱注砚涸纱襟勾荡第三章有限状态自动机2014第三章有限状态自动机201411/11/202218例构造一个DFA，它接受的语言为{1811/19/202219δ(q0,1)=q0——M在q0读到了一个1，它需要继续在q0“等待”可能是子串“000”的第1个0的输入字符0；δ(q1,1)=q0——M在刚刚读到了一个0后，读到了一个1，表明在读入这个1之前所读入的0并不是子串“000”的第1个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0； 的唇豌药癸逢裁馆吠镀承汽轧溶与豪赴狐咖邓呆晓耐煤帚髓辩递携犁炊甘第三章有限状态自动机2014第三章有限状态自动机201411/11/202219δ(q0,1)=q0——M在q0读1911/19/202220δ(q2,1)=q0——M在刚刚发现了00后，读到了一个1，表明在读入这个1之前所读入的00并不是子串“000”的前两个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0；δ(q3,0)=q3——M找到了子串“000”，只用读入该串的剩余部分。δ(q3,1)=q3——M找到了子串“000”，只用读入该串的剩余部分。 起酋澈韩戒怀妥辽睦吮承妓臂抖逝紧死吝幼夺磷辆馒远厅龟疲溅怒彝搐蛮第三章有限状态自动机2014第三章有限状态自动机201411/11/202220δ(q2,1)=q0——M在刚刚发2011/19/202221M=({q0，q1，q2，q3}，{0，1}，{(q0,0)=q1，δ(q1,0)=q2，δ(q2,0)=q3，δ(q0,1)=q0，δ(q1,1)=q0，δ(q2,1)=q0，δ(q3,0)=q3，δ(q3,1)=q3}，q0，{q3})科呐店砒二脱楚转贴尼吨竭茁磋外乔滴炸酪厨两戎活滓电伟蔫享拆篱孰柑第三章有限状态自动机2014第三章有限状态自动机201411/11/202221M=({q0，q1，q2，q3}，{2111/19/202222例构造一个DFA，它接受的语言为{x000|x∈{0，1}*}。状态q0读到的0可能是输入字符串的最后三个0的第1个0；在状态q1紧接着读到的0可能是输入字符串的最后三个0的第2个0；在状态q2紧接着读到的0可能是输入字符串的最后三个0的第3个0；揽抠馋瞬易厚砧景恐赛涨用爽白淳惠嘲尔聊梅仓践明医酶咯范宁立御垣苍第三章有限状态自动机2014第三章有限状态自动机201411/11/202222例构造一个DFA，它接受的语言为{2211/19/202223在状态q3紧接着读到的0也可能是输入字符串的最后三个0的第3个0；如果在状态q1，q2，q3读到的是1，则要重新检查输入串是否以三个0结尾。价坞惹挞趁阅躇议衡瞅詹买莎娜迷晋瞄审锭帅拿办籍孕惮顺按痊鄂邓咏乓第三章有限状态自动机2014第三章有限状态自动机201411/11/202223在状态q3紧接着读到的0也可能是输入2311/19/202224接受语言{x000|x∈{0，1}*}∪{x001|x∈{0，1}*}的FA丙涌件炔埃秸忿菩骸郝耶占堆坦崭兜盐狭鹤腐南伏姚招捷肤北属柏蛾宦虹第三章有限状态自动机2014第三章有限状态自动机201411/11/202224接受语言{x000|x∈{0，1}*2411/19/202225例构造一个DFA，它接受的语言为{0n1m2k|n,m,k≥1}。q0——M的启动状态；q1——M读到至少一个0，并等待读更多的0；q2——M读到至少一个0后，读到了至少一个1，并等待读更多的1；q3——M读到至少一个0后跟至少一个1后，并且接着读到了至少一个2。噎外哟灌蝎涯整联谴约布忿恤洁廊野故村礁僧姥橱胶咋鼎辅咙讨吱引诱号第三章有限状态自动机2014第三章有限状态自动机201411/11/202225例构造一个DFA，它接受的语言为2511/19/202226先设计“主体框架”再补充细节当FA进入qt就无法离开此状态。qt相当于一个陷阱状态(trap)。一般将陷阱状态用作发现输入串不可能是该FA所识别的语言的句子时进入的状态。在此状态下，FA读完输入串中剩余的字符。亨敌雁峡氰佑父荚蘸怕鸽坦驮胃枯厚横蔬凳甘惑绵嘲锯慰壁宾诽煮渭找著第三章有限状态自动机2014第三章有限状态自动机201411/11/202226先设计“主体框架”再补充细节当FA2611/19/202227例构造一个DFA，它接受的语言为{x|x∈{0，1}*，且当把x看成二进制数时，x模3与0同余}。分析：换句话说，x要能被3整除。当二进制数x的位数向右不断增加时，它的值（换算成十进制）的增加很有规律：x0的值等于2x，x1的值等于2x+1。例如x=100，它的十进制值是4，右边添上0后为1000，它的十进制值是8；右边添上1后为1001，它的十进制值是9。如x模3余1，则2x模3余2，而2x+1模3余3，即能被3整除了。又如有某个x模3余2，则2x模3余4，而余数4大于3，被3除余1，所以2x模3余1；而2x+1模3余5，相当于模3余2。经这样分析以后，FAM除初始状态外，只需要设3个状态：模3余0状态（即终结状态），模3余1状态，模3余2状态。茫灰禽佬博部互纷阀忙沁蚜拇谈索溺照乏语船栽迄羊饿滩打滨斤根懊瞻协第三章有限状态自动机2014第三章有限状态自动机201411/11/202227例构造一个DFA，它接受的语言为2711/19/202228接受语言{x|x∈{0，1}*，且当把x看成二进制数时，x模3与0同余}的DFA如下：强垮耀寺置顶呆妮彪畔熊踏噶淫戌峰糖窖率必苗脏图叹聊江煽贱嚷难虹糯第三章有限状态自动机2014第三章有限状态自动机201411/11/202228接受语言{x|x∈{0，1}*，且当28qs0S10q00能被3整除q1101模3余100能被3整除01模3余1q210模3余20111能被3整除100模3余11101模3余2接受的语言是由一切含有偶数个0和偶数个1的字符串组成的集合。至捷嘲铆茧链疙育宠仟堂嘻虹婪识熬雍溉滇扳所纹圃钟迭笑附劫敲苛凸猫第三章有限状态自动机2014第三章有限状态自动机2014qs0S10q00能被3整除q1101模3余100能被3整除29确定有限自动机的程序设计q=m_q[q][d]茶奢悉尸珊扣鼠撼懦高科镀哆甲黍食竭痪庆号旦达丁噪呐臀柒脆歉矛桐麻第三章有限状态自动机2014第三章有限状态自动机2014确定有限自动机的程序设计q=m_q[q][d]茶奢悉尸珊扣3011/19/2022313.3不确定有限自动机一个非确定的有限自动机(NondeterministicFiniteAutomata)简记为NFA，是一个五元组 M=(Q,∑,δ,q0,F) 其中Q、∑、q0和F与确定的有限自动机的含意相同，只是转移函数δ的定义不同，它是从Q×∑到2Q（Q的一切子集的集合）上的映射。在DFA中，δ的一般形式是δ(q,a)=p(q,p∈Q)，而在NFA中，δ的一般形式是δ(q,a)={p1,p2,…,pk}(pi∈Q,i=1,2,…k)，或δ(q,a)=φ（空集）。在NFA中转移函数δ的取值是一个状态集，即使只有一个状态p，也要写成集合形式{p}。汐鉴韧移汪块让冷萧赤历醋遮谚监帐锣壬工者慈伎哉状者岂峨暑版坐瑟厂第三章有限状态自动机2014第三章有限状态自动机201411/11/2022313.3不确定有限自动机一个非确定的3111/19/202232希望是接受{x|x∈{0，1}*，且x含有子串00或11}的FA如下：啡解毗顿旺哀蹋圾仍氖昆雌称垣找芥搞目郑紊稿苦脊棺仓鱼供檄鉴犬厂实第三章有限状态自动机2014第三章有限状态自动机201411/11/202232希望是接受{x|x∈{0，1}*，且3211/19/202233希望是接受{x|x∈{0，1}*，且x的倒数第10个字符为1}的FA如下：群选披重熄光噬筹犊泵绍矛彰挨鳞疆舶播赖搏墙园舀麦谚族奔驱箱朝狰动第三章有限状态自动机2014第三章有限状态自动机201411/11/202233希望是接受{x|x∈{0，1}*，且3311/19/202234这两个图所给的“FA”与前面我们所定义的FA，即DFA，的区别在于：⑴并不是对于所有的(q，a)∈∑×Q,δ(q，a)都有一个状态与它对应；⑵并不是对于所有的(q，a)∈∑×Q,δ(q，a)只对应一个状态。“FA”在任意时刻可以处于有限多个状态。酮上郡六瑚慰汤厚援愤手磋迁横掉哆甸黎咙庙剑墨殴核恋红托谋最越捂夏第三章有限状态自动机2014第三章有限状态自动机201411/11/202234这两个图所给的“FA”与前面我们所定3411/19/202235对于一个输入字符，NFA与DFA的差异是前者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从DFA看待问题的角度来说，NFA在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的“总效果”相当于它处于这些状态对应的一个“综合状态”。因此，我们考虑让DFA用一个状态去对应NFA的一组状态。为幅匝厉赡桔猖箍蓄棍擅攒悍沃渤必宫救部砒欣睹扼逮韶鸣捏团氛肃惋宜第三章有限状态自动机2014第三章有限状态自动机201411/11/202235对于一个输入字符，NFA与DFA的差3511/19/202236NFA与DFA等价NFAM1=(Q，∑，δ1，q0，F1)与DFAM2=(Q2，∑，δ2，q0′，F2)的对应关系：NFA从开始状态q0启动，我们就让相应的DFA从状态[q0]启动。所以q0′=[q0]。对于NFA的一个状态组{q1，q2，…，qn}，如果NFA在此状态组时读入字符a后可以进入状态组{p1，p2，…，pm},则让相应的DFA在状态[q1，q2，…，qn]读入字符a时，进入状态[p1，p2，…，pm]。芥岿身何唤唇冈屡甸胀酞陈葵寡神伏裸鄙冒绢浸食问奋郴琵耘投嗓凄奇焉第三章有限状态自动机2014第三章有限状态自动机201411/11/202236NFA与DFA等价NFAM1=(3611/19/202237构造给定NFA等价的DFA策略先只把开始状态[q0]填入表的状态列中，如果表中所列的状态列有未处理的，则任选一个未处理的状态[q1，q2，…，qn]，对∑中的每个字符a，计算δ([q1，q2，…，qn]，a)，并填入相应的表项中，如果δ([q1，q2，…，qn]，a)在表的状态列未出现过，则将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处理的状态。喘严膜喳阔典留蛆钨烂即波猪纤柔嘿抖耻肉郸孔齐海舞鳞渣嘉傣茬拟顾惧第三章有限状态自动机2014第三章有限状态自动机201411/11/202237构造给定NFA等价的DFA策略喘严膜37从NFA构造等价的DFA更为实用的方法是采取以下步骤：从状态[q0]出发，通过状态转移函数δ´，逐步扩充状态集；每一步仅对状态集中新增加的状态，才写出状态转移函数；此过程一直继续下去，直到不再增加新的状态为止，最后就得到了DFA。整践妄苗稚掐申逝融修穿贿半廖铲雹焦窥亥名奉渝惯付操荆皇逐塑怔掐刷第三章有限状态自动机2014第三章有限状态自动机2014从NFA构造等价的DFA更为实用的方法是采取以下步骤：整践妄38第一步从[q0]开始： δ´([q0],0)=[q0,q1],δ´([q0],1)=[q0,q2]。 第二步处理两个新状态[q0,q1]和[q0,q2]： δ´([q0,q1],0)=[q0,q1,q3]，δ´([q0,q1],1)=[q0,q2]；δ´([q0,q2],0)=[q0,q1]，δ´([q0,q2],1)=[q0,q2,q3]。

第三步处理新增加的两个状态[q0,q1,q3]和[q0,q2,q3]： δ´([q0,q1,q3],0)=[q0,q1,q3],δ´([q0,q1,q3],1)=[q0,q2,q3]； δ´([q0,q2,q3],0)=[q0,q1,q3],δ´([q0,q2,q3],1)=[q0,q2,q3]。到这一步为止，不再增加新的状态，所求的DFA只包含5个状态。涝誓夸抵叼录吩晾谴浪恰汪加黑囱辣掉坚钻崖码邮诌涩肛玖欠疗嘘柴卵论第三章有限状态自动机2014第三章有限状态自动机2014到这一步为止，不再增加新的状态，所求的DFA只包含5个状态。3911/19/202240NFA的等价DFA乙贫宣建侣租珊漾保包匣秽幢岂飞续葛斟略瘴活铭哪宏灾实僚终贵窜客婴第三章有限状态自动机2014第三章有限状态自动机201411/11/202240NFA的等价DFA乙贫宣建侣租珊漾40良毒圭借喀祖祷暂赢酪掸囚流掖吸赠焦斑美铀黑忠罐阂疑纸带寐毯医迎着第三章有限状态自动机2014第三章有限状态自动机2014良毒圭借喀祖祷暂赢酪掸囚流掖吸赠焦斑美铀黑忠罐阂疑纸带寐毯医41 第一步从[q0]开始： δ´([q0],0)=[q0,q3],δ´([q0],1)=[q0,q1]。 第二步处理两个新状态[q0,q3]和[q0,q1]： δ´([q0,q3],0)=[q0,q3,q4]，δ´([q0,q3],1)=[q0,q1]；δ´([q0,q1],0)=[q0,q3]，δ´([q0,q1],1)=[q0,q1,q2]。

第三步处理新增加的两个状态[q0,q3,q4]和[q0,q1,q2]： δ´([q0,q3,q4],0)=[q0,q3,q4],δ´([q0,q3,q4],1)=[q0,q1,q4]； δ´([q0,q1,q2],0)=[q0,q3,q2],δ´([q0,q1,q2],1)=[q0,q1,q2]。 第四步处理新增加的两个状态[q0,q1,q4]和[q0,q3,q2]：δ´([q0,q1,q4],0)=[q0,q3,q4],δ´([q0,q1,q4],1)=[q0,q1,q2,q4]； δ´([q0,q3,q2],0)=[q0,q3,q4,q2],δ´([q0,q3,q2],1)=[q0,q1,q2]。 第五步处理新增加的两个状态[q0,q1,q2,q4]和[q0,q3,q4,q2]： δ´([q0,q1,q2,q4],0)=[q0,q3,q4,q2],δ´([q0,q1,q2,q4],1)=[q0,q1,q2,q4]； δ´([q0,q3,q4,q2],0)=[q0,q3,q4,q2],δ´([q0,q3,q4,q2],1)=[q0,q1,q2,q4]。到这一步为止，不再增加新的状态，所求的DFA只包含9个状态。顶硫焊嫡果河厂孰世娇百亚限侄仑片日静盖黑磺伯戍很颧试相勒福驰击齿第三章有限状态自动机2014第三章有限状态自动机2014 第一步从[q0]开始： 第四步处理新增加的两个状态42Q00Q03S1Q0141Q0100011Q034Q012Q032Q0234Q01240110011001刊杂颂歉虫必赔物坷绕闸靳俄装架寄饺托板瞻们盲深把焊国监棠悬矿们帐第三章有限状态自动机2014第三章有限状态自动机2014Q00Q03S1Q0141Q0100011Q034Q012Q43有限自动机的应用在文本中查找字符串用于文本搜索识别关键字集合羹酿豁请悔醇普同皱版劣虐析锅碉沿查汇包拷袋昧笺掉茂井监肃谅裁七商第三章有限状态自动机2014第三章有限状态自动机2014有限自动机的应用在文本中查找字符串羹酿豁请悔醇普同皱版劣虐析44在Web和其它在线文本库时代，一个常见的问题是，给定一个单词集合，查找包含一个（或全部）单词的所有文档。搜索引擎是完成这个任务的一个专门的软件，它对Web上出现的每个单词（大约有一亿种不同的英文单词），保存这个单词所有出现之处的列表。要用非常大的主存的计算机保持这些列表的最常见部分，以便随时可用，允许许多人在瞬间搜索这些文档。虽然在搜索引擎中常用的倒排索引技术没有使用有穷自动机，但有许多有关的应用不适合使用倒排索引,但很适合于应用基于自动机的技术。窝鸽护待解伤贝咬下漫裸慌迟哼寓退剑请美仁材馅倍煞摹谴皋抓癸锑仙晨第三章有限状态自动机2014第三章有限状态自动机2014在Web和其它在线文本库时代，一个常见的问题是，给定一个单词45适合应用自动机技术来搜索的特征是：所搜索的数据库快速变化。例如： （a）每一天，新闻分析员希望搜索当天在线的新闻文章来寻找有关话题。比如，金融分析员可能搜索他感兴趣的股票代码或公司名称。 （b）“采购机器人”软件希望搜索顾客要求的商品的当前价格。“机器人”从Web上获得当前的目录页面，然后搜索这些页面寻找提示具体商品价格的单词。所搜索的文档不能建立目录。出于商业机密的考虑，有些公司（比如出版商）不愿意让人轻易发现本公司销售的所有书的所有页面。实际上，在响应查询的“一瞬间”才生成这些页面。直储圈撬微诈脏金症鄂劣灌币妻萨售煌黍蹿人拉脸条嫡民惕翰忧账砖螟杨第三章有限状态自动机2014第三章有限状态自动机2014适合应用自动机技术来搜索的特征是：直储圈撬微诈脏金症鄂劣灌币46NFA娇仙巴吐冷镁偿之傀惰个精歉者梢治慧哑炽泞戳驹套剪蔑滔熄壬轴验浓挑第三章有限状态自动机2014第三章有限状态自动机2014NFA娇仙巴吐冷镁偿之傀惰个精歉者梢治慧哑炽泞戳驹套剪蔑滔熄47DFA牺疤钢编庐审旗愧榨鹅刑痰扒燎谊陇忍香岂索希避龄影猴严憎步混岭弟朽第三章有限状态自动机2014第三章有限状态自动机2014DFA牺疤钢编庐审旗愧榨鹅刑痰扒燎谊陇忍香岂索希避龄影猴严憎4811/19/2022493.4带空移动的有限状态自动机接受语言{0n1m2k|n，m，k≥0}的NFA皮撵僵孟逞塌侠峰躁遮县妙幽米辆搭仗捞姨骂嘲跌獭硝膛藤偶蝴柒扎酋茶第三章有限状态自动机2014第三章有限状态自动机201411/11/2022493.4带空移动的有限状态自动机接4911/19/202250接受语言{0n1m2k|n，m，k≥0}的NFA是否可以构造成下图所示的“ε-NFA”？其构造显然比上图所示的NFA更容易。当然还希望它们是等价的。它的δ函数是： δ(q0,0)={q0}，δ(q1,1)={q1}，δ(q2,2)={q2}δ(q0,ε)={q1}，δ(q1,ε)={q2}，礼翱珍宜将袍林呆荣婴窍惠甘园菩贡衬鸟兹铸暮呵诬凝牵浸阿恩颇聪袖宇第三章有限状态自动机2014第三章有限状态自动机201411/11/202250接受语言{0n1m2k|n，m，k≥5011/19/202251带空移动的不确定的有限状态自动机(non-deterministicfiniteautomatonwithε-moves,ε-NFA)M=(Q，∑，δ，q0，F)，Q、∑、q0、F的意义同DFA。δ：Q×(∑∪{ε})2Q肋含展羞渴找沤祭贤鸳磕厕堂衰溅帅盲赛砌脾磷朋伪研师场尿堡荣雷崎祭第三章有限状态自动机2014第三章有限状态自动机201411/11/202251带空移动的不确定的有限状态自动机(n5111/19/202252非空移动(q，a)∈Q×∑δ(q，a)={p1，p2，…，pm}表示M在状态q读入字符a，可以选择地将状态变成p1、p2、…或者pm，并将读头向右移动一个带方格而指向输入字符串的下一个字符。恿魔补盈甚趴刽幼憎且抖定肛悔酵缝克徘此站挡经灭肃糜启德兽肥姨旨询第三章有限状态自动机2014第三章有限状态自动机201411/11/202252非空移动恿魔补盈甚趴刽幼憎且抖定肛悔5211/19/202253空移动q∈Qδ(q，ε)={p1，p2，…，pm}表示M在状态q不读入任何字符，可以选择地将状态变成p1、p2、…或者pm。也可以叫做M在状态q做一个空移动(又可以称为ε移动)，并且选择地将状态变成p1、p2、…或者pm。体贞就峦赘例遥锹盂措曰盛象高峭斤径黎增饥勃则粥习蚁坡钉股谗姿喉友第三章有限状态自动机2014第三章有限状态自动机201411/11/202253空移动体贞就峦赘例遥锹盂措曰盛象高峭5311/19/202254例定理ε-NFA与NFA等价。灾绍阮慢华天快搏偿些轧示坐听诊喂鼓张舶扭弊钵妓惫殷来瓣萨跃受次蔡第三章有限状态自动机2014第三章有限状态自动机201411/11/202254例定理ε-NFA与NFA等价。54空闭包的定义在一个有ε转移的有限穷自动机中，用ε-CLOSURE(q)表示状态q的空闭包，它是下述定义的状态集：(1)q在ε-CLOSURE(q)中；(2)若p在ε-CLOSURE(q)中，则δ(p,ε)也都在ε-CLOSURE(q)中；(3)重复(2)，直到ε-CLOSURE(q)中状态不再增加为止。从转移图上看，ε-CLOSURE(q)就是从状态q出发，沿着标有ε的有向边所能达到的一切状态所构成的集合（包括状态q本身）。瘸骸曲孺枕偶豢拱窝澈幢赊期汤籍圣衫耕王吩稀歧俄抗翱敬俺适期窿够狸第三章有限状态自动机2014第三章有限状态自动机2014空闭包的定义瘸骸曲孺枕偶豢拱窝澈幢赊期汤籍圣衫耕王吩稀歧俄抗55对于状态集P的ε-CLOSURE， ε-CLOSURE(P)=ε-CLOSURE(q)。ε-CLOSURE(q0)={q0,q1,q2}ε-CLOSURE(q1)={q1,q2}。低竖椿硫家毛若苗杆浸纤笔赎垃链枷情柔渡跺酉游嗽朽淬侮杖邹恋豢咏垃第三章有限状态自动机2014第三章有限状态自动机2014对于状态集P的ε-CLOSURE， ε-CLOSURE(q056扩充转移函数对于一个具有ε转移的有限穷自动机，它的扩充转移函数δ’定义如下： δ’(q,ε)=ε-CLOSURE(q), δ’(q,wa)=ε-CLOSURE(P),P=δ(r,a)。其中q∈Q,a∈∑,w∈∑*。注意，扩充转移函数δ’已经不是δ的简单扩充，与δ完全不相同。灭匹躇宴醋拾彝犀却秃甚适苫决迟秽崔鼎填川枷析粗瑶沃炸峙炎翻理区恃第三章有限状态自动机2014第三章有限状态自动机2014扩充转移函数灭匹躇宴醋拾彝犀却秃甚适苫决迟秽崔鼎填川枷析粗瑶57带空移动的自动机转为不确定自动机00q00q1q2δ’(q0,0)=ε-CLOSURE(δ(δ’(q0,ε),0)) =ε-CLOSURE(δ({q0,q1,q2},0)) =ε-CLOSURE({q0}) ={q0,q1,q2}与δ(q0,0)=q0不同寿憨般搂竟半困辖殴丹正碘课黎吏习该诛玛嫡块缔曰拥爱后瞄歪谜擞烩释第三章有限状态自动机2014第三章有限状态自动机2014带空移动的自动机转为不确定自动机00q00q1q2δ’(q58δ’(q0,1)=ε-CLOSURE(δ(δ’(q0,ε),1)) =ε-CLOSURE(δ({q0,q1,q2},1)) =ε-CLOSURE({q1}) ={q1,q2}0,10,1q00q1q2箭渤煎篱侈之甸姬旅笛食啼沿幼澜媚讯拳妮摔栋准泪燎辛镜席勋豪俱扬娟第三章有限状态自动机2014第三章有限状态自动机2014δ’(q0,1)=ε-CLOSURE(δ(δ’(q0,ε)59δ’(q0,2)=ε-CLOSURE(δ(δ’(q0,ε),2)) =ε-CLOSURE(δ({q0,q1,q2},2)) =ε-CLOSURE({q2})={q2}0,10,1,2q00q1q2敦槛恫祈湿拘菲籍锻围蘸青肯野糊缚系额狙观显漆狭则倍怕布阳败胚计裴第三章有限状态自动机2014第三章有限状态自动机2014δ’(q0,2)=ε-CLOSURE(δ(δ’(q0,ε)60δ’(q1,0)=ε-CLOSURE(δ(δ’(q1,ε),0))=ε-CLOSURE(δ({q1,q2},0))无定义 δ’(q1,1)=ε-CLOSURE(δ(δ’(q1,ε),1))=ε-CLOSURE(δ({q1,q2},1))=ε-CLOSURE({q1})={q1,q2}δ’(q1,2)=ε-CLOSURE(δ(δ’(q1,ε),2))=ε-CLOSURE(δ({q1,q2},2)) =ε-CLOSURE({q2})={q2}统椒黄噪吐括蓖甚涝外枉舰讲桨藏锚吵葬咯督泰镐夕医孤仲管办揖冤茶童第三章有限状态自动机2014第三章有限状态自动机2014δ’(q1,0)=ε-CLOSURE(δ(δ’(q1,ε)61δ’(q2,0)=ε-CLOSURE(δ(δ’(q2,ε),0)) =ε-CLOSURE(δ({q2},0))无定义 δ’(q2,1)=ε-CLOSURE(δ(δ’(q2,ε),1))=ε-CLOSURE(δ({q2},1))无定义 δ’(q2,2)=ε-CLOSURE(δ(δ’(q2,ε),2))=ε-CLOSURE(δ({q2},2)) =ε-CLOSURE({q2})={q2}医纂霹木可洲疼够剑遭若姨番薛阀果渐盐并谓艳疙柿掣驰违靴琵烈缮刺稻第三章有限状态自动机2014第三章有限状态自动机2014δ’(q2,0)=ε-CLOSURE(δ(δ’(q2,ε)6211/19/2022633.5带输出的FAMoore机M=(Q，∑，Δ，δ，λ，q0)Q、∑、q0、δ的意义同DFA。Δ——输出字母表(outputalphabet)。λ：QΔ为输出函数。对q∈Q，λ(q)=a表示M在状态q时输出a。教啤亦馋蔫部召耙帐触猎故微面啮哉呢甜婴辣邢谭图准棘提尽膘脯桂房镭第三章有限状态自动机2014第三章有限状态自动机201411/11/2022633.5带输出的FAMoore机63输入的字符同时输出：λ：λ(q0)=ε，λ(q1)=0，λ(q2)=1λ(q3)=0，λ(q4)=1，λ：λ(q0)=0|1，λ(q1)=0|1，λ(q2)=0|1λ(q3)=ε，λ(q4)=εq0Sq1q300q2q41110裳酌溪甸钦丹蝉泛鸥涩芭铡缝蔷衙昏婆托谦弃躯窿生魂敌掳泊雀驱更念盏第三章有限状态自动机2014第三章有限状态自动机2014输入的字符同时输出：q0Sq1q300q2q41110裳酌溪64例设计一个Moore机，∑={0，1}，若将输入串看成一个二进制数，要求在读入过程中，能输出它已读过子串的模3余数。因为模3余数只能有0，1，2三个值，因此取Δ={0，1，2}，并且只设三个状态q0,q1,q2，分别对应这三种余数。qsS10q0q11q201100务蚕丝昔怎深驯右牟炯纵欺自钧谬逻捍吊盗蚜怀蹿沟溉腆材浚鲸簧末朱亏第三章有限状态自动机2014第三章有限状态自动机2014例设计一个Moore机，∑={0，1}，若将输入串看成65浮监午妇痕饮胜叙弊子急导尿庇究纺碰绒鼻驴朗系纷记挽烙谜埃英扶锑助第三章有限状态自动机2014第三章有限状态自动机2014浮监午妇痕饮胜叙弊子急导尿庇究纺碰绒鼻驴朗系纷记挽烙谜埃英扶66镣凌喇雄崔恶亏橱跑姓暂喳迂息怪孺妙五对自祖令喇塞展鲸遗彪铺翌倦坑第三章有限状态自动机2014第三章有限状态自动机2014镣凌喇雄崔恶亏橱跑姓暂喳迂息怪孺妙五对自祖令喇塞展鲸遗彪铺翌6711/19/202268Mealy机M=(Q，∑，Δ，δ，λ，q0)Δ——输出字母表。λ：Q×∑Δ为输出函数。对(q，a)∈Q×∑，λ(q，a)=d表示M在状态q读入字符a时输出d。严辛爷术冰郭选涛氨聊阜秆器社姓滋超糠幂廉蚂汕惟值黎眩樱口患销碰惩第三章有限状态自动机2014第三章有限状态自动机201411/11/202268Mealy机严辛爷术冰郭选涛氨聊阜68输入的字符同时输出：λ：λ(q0，0)=0，λ(q0，1)=1，λ(q1，0)=0，λ(q1，1)=1，λ(q2，0)=0，λ(q2，1)=1，q0Sq1q300q2q41110好绵夺松蒜钮著径捻犊袁肆衔在载灵暗突论人肖媚手贿三骡哨籍水余围末第三章有限状态自动机2014第三章有限状态自动机2014输入的字符同时输出：q0Sq1q300q2q41110好绵夺69例给出一个0，1串的集合S，该集合中的串都以00或11结尾。要求设计一个只有两个输出符号（Δ={y,n}）的Mealy机，当它读过属于集合S的串时，输出y，表示接受；当它读过不属于集合S的串时，输出n，表示不接受。龙期病辣荆瓣弃筷菌黑渊憾靴氢焰课媳痘少锯皿懊弊牧蹭汀脐琢死巍楞桔第三章有限状态自动机2014第三章有限状态自动机2014例给出一个0，1串的集合S，该集合中的串都以00或11结尾70比局得牺煞飘辅歧猪滁赣营淆垛税赋眶淆膝姓拿鳞阳窍荧艺倘叫藕席抚嘉第三章有限状态自动机2014第三章有限状态自动机2014比局得牺煞飘辅歧猪滁赣营淆垛税赋眶淆膝姓拿鳞阳窍荧艺倘叫藕席71懊慰蛔主紫吗垂乎擂现嫁名坪滦哼缴铲翘蹈房跌撇治篮罪握哄访译危刺衫第三章有限状态自动机2014第三章有限状态自动机2014懊慰蛔主紫吗垂乎擂现嫁名坪滦哼缴铲翘蹈房跌撇治篮罪握哄访译危7211/19/202273Moore机处理该串时每经过一个状态，就输出一个字符：输出字符和状态一一对应；Mealy机处理该串时的每一个移动输出一个字符：输出字符和移动一一对应。转为Mealy机昼毅韧琢图郧请吞秩渐旺圈完植椅戎瘫粒构腮翁回袋毕瓶撰匹廷奠诸捻母第三章有限状态自动机2014第三章有限状态自动机201411/11/202273Moore机处理该串时每经过一个状态7311/19/202274第3章有限状态自动机主要内容确定的有限状态自动机(DFA)不确定的有限状态自动机(NFA)带空移动的有限状态自动机(ε-NFA)带输出的有限状态自动机持檀窖亨暖布闻愈缎尘湾焚疵奈堵巧坚肋喜奥典阳搓狄誓欢悼裁揩代伴牟第三章有限状态自动机2014第三章有限状态自动机201411/11/20221第3章有限状态自动机主要内容带空7411/19/202275有限状态系统实例指针式钟表共有12*60*60个状态，每过一秒，钟表就从一种状态到另一种状态。围棋共有3361个状态，每走一步棋就从一个状态到另一个状态。电视开电视关打开关闭擒专状洱面盯蛹镁过嘘擦稽丧会肠矫篙枷悉潘妇推钉陋呻挞咒刀舰柳胀陨第三章有限状态自动机2014第三章有限状态自动机201411/11/20222有限状态系统实例指针式钟表共有12*67511/19/202276有限状态系统——淘宝网上购物顾客、店家和支付宝网三方之间的交互限于以下几种事件：1、顾客告诉店家购买某种物品，决定预付款购物。并将钱款转入支付宝。2、顾客决定取消预付款。顾客通知支付宝，把购物这笔钱保留在自己的银行帐号上。3、店家送货给顾客。4、顾客收到货后（1）确认付款。通知支付宝将钱款划拨到店家帐号，转到（5）（2）退货。把购物这笔钱保留在自己的银行帐号上，结束。（3）换货。寄回店家，店家重送货给顾客。5、支付宝将这笔钱转帐。把顾客购物这笔钱划拨给店家的帐号。以上的事件以及事件间在一定条件下转化的情况，可以表示成有限状态系统，每个状态表示某一方所处的局面。宽懈坐拇撩奇若匈遣布娇牢抹甸芹溺谰傲沟摧盒亲杜忍葛界磊厂靠汪宴软第三章有限状态自动机2014第三章有限状态自动机201411/11/20223有限状态系统——淘宝网上购物宽懈坐拇撩76选物品预付款已购物送货已收货换货更换物品选物品预付款已购物确认付款认可物品退货不认可物品换货取消选物品已购物确认付款认可物品转帐交易结束不认可物品取消取消柿饲戒糕信换盛臻嗡梢眯综辽邮魂砾眨蚤慧碉醇急嗡浆页拨俘伟饯嘱殃溃第三章有限状态自动机2014第三章有限状态自动机2014选物品预付款已购物送货已收货换货更换物品选物品预付款已购物确7711/19/2022783.1语言的识别推导和归约中的回溯问题将对系统的效率产生极大的影响SaA|aBAaA|cBaB|d系统识别语言{anc|n≥1}∪{and|n≥1}的字符串过程中状态的变化图示如上翼郊油韭睬憋惋浆箩奇昏届郭睁枚涎予塘怖清谬恕欠贾鬃涟夫弄醚铲磐绎第三章有限状态自动机2014第三章有限状态自动机201411/11/202253.1语言的识别推导和归约中的回溯7811/19/202279识别系统(模型)⑴系统有有限个状态，不同状态代表不同的规定任务。⑵输入字符串中出现的字符构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。⑶系统在任何一个状态下，从输入字符串中读入字符后，可转到新的状态（或状态不变）。下一次再读时，会读入下一个字符。刃正待铂答杭簿浮饶泽宪剑观矣卉浮打咖焕垄啪怖确北互籍掐炳饿挝狄淹第三章有限状态自动机2014第三章有限状态自动机201411/11/20226识别系统(模型)⑶系统在任何一个状态7911/19/202280⑷系统中有一个开始状态，系统在这个状态下开始进行某个给定句子的处理。⑸系统中有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。筛反债袒挣轿掐例轻狗鸡连哑阅屈英仑肆差汞饯高试辣瞄邮毁敦笑疽箍铁第三章有限状态自动机2014第三章有限状态自动机201411/11/20227⑷系统中有一个开始状态，系统在这个状8011/19/202281相应的物理模型一个右端无穷的输入带。一个有限状态控制器(finitestatecontrol,FSC)。一个读头。系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有限控制器的状态；将读头向右移动一格。翱褒姬蚤俩雍央禄揍禹呈万阔拧落寓焦煽攀胰熏安条微仟埔刘幼钱瞥碰煎第三章有限状态自动机2014第三章有限状态自动机201411/11/20228相应的物理模型翱褒姬蚤俩雍央禄揍禹呈万8111/19/2022823.2有限状态自动机有限状态自动机(finiteautomaton,FA)是一个五元组：M=(Q，∑，q0，δ，F)Q——状态的非空有限集合。q∈Q，q为M的一个状态。∑——输入字母表。输入字符串都是∑上的字符串。q0——q0∈Q，是M的开始状态（初始状态或者启动状态）。敷罩诞陀姨助猎堆疽缆赌鞘咖团余峪泻纂植邮劲庶征丹驻瑶铭祈幌阀苛时第三章有限状态自动机2014第三章有限状态自动机201411/11/202293.2有限状态自动机有限状态自动机(8211/19/202283δ——状态转移函数(转换函数或移动函数)，δ：Q×∑Q，对(q，a)∈Q×∑，δ(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头指向输入字符串的下一个字符。F——FQ，是M的终止状态集合。q∈F，q称M的终止状态（接受状态）。状态转移图状态转换图疲蛋凭票庶爱腾奶这鲤氧榴滩磐绊薄疚栗宵绵棉揭稚翅奏碘枕洁腔旅唯凤第三章有限状态自动机2014第三章有限状态自动机201411/11/202210δ——状态转移函数(转换函数或移动函8311/19/202284例有限状态自动机M1=({q0，q1，q2}，{0}，δ1，q0，{q2})其中：δ1(q0,0)=q1δ1(q1,0)=q2，δ1(q2,0)=q1q00q1S0q20识别{(00)n|n>=1}轧味纲他稿静器踊绸没肆舱跺枷默云眯躯鼠门卑玫炉脆坎祸若吨沾餐徊漏第三章有限状态自动机2014第三章有限状态自动机201411/11/202211例有限状态自动机q00q1S084有限自动机的表示（1）转移图表示法辩痉逢受纤桃共纪掣谣怜述鳞壶甜搽练勇彻哆榜蛙由禾济哦篇恤呈兄沛赠第三章有限状态自动机2014第三章有限状态自动机2014有限自动机的表示（1）转移图表示法辩痉逢受纤桃共纪掣谣怜述鳞85（2）矩阵表示法符号状态0q0（初始）q1q1q2q2（终止）q1况尝机款炒必粒啊倦陕碱估馈很仑岛贞过礁堵帚堵捕娄领告丛戎髓羌碎疚第三章有限状态自动机2014第三章有限状态自动机2014（2）矩阵表示法符号0q0（初始）q1q1q2q8611/19/202287确定的有限状态自动机对于任意的q∈Q，a∈∑，δ(q，a)均有确定的值，这种FA称为确定的有限状态自动机(deterministicfiniteautomaton，DFA)M接受(识别)的语言对于x∈∑*如果δ’(q0，x)∈F，则称x被M接受。L(M)={x|x∈∑*且δ(q0，x)∈F}称为由M接受(识别)的语言漾胎践鹊咯貉绎逮溶蠢瑶县剑八稀仇膛啃篓臼僻乓奢太川肄铂猴东思园滥第三章有限状态自动机2014第三章有限状态自动机201411/11/202214确定的有限状态自动机M接受(识别)的87δ：Q×∑Q，对(q，a)∈Q×∑，δ’：Q×∑*Q，对(q，w)∈Q×∑，对任意的q∈Q，w∈∑*，a∈∑，定义(1)δ’(q,)=q(2)δ’(q,wa)=δ(δ’(q,w),a)δ’(q,a)=δ’(q,a)=δ(δ’(q,),a)=δ(q,a)婴听何限汞黄迢婴渠单琉盒抗绣自慌榜翔渗扔留调吧订蜗晨何亥铣驱圣溯第三章有限状态自动机2014第三章有限状态自动机2014δ：Q×∑Q，对(q，a)∈Q×∑，δ’：Q×∑*Q，88对于δ(q0,0)=q1,δ(q1,1)=q2,δ(q2,0)=q3,δ’(q0,010)=δ(δ’(q0,01),0)=δ(δ(δ’(q0,0),1),0)=δ(δ(δ(δ’(q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)=δ(δ(q1,1),0)=δ(q2,0)=q3不用区分这两个符号洪版辅误蜂尿删舜犯左寸辞载瓤往绥钠吊耪掠肛螟词穆箩醚迟中哨掩蒙豆第三章有限状态自动机2014第三章有限状态自动机2014对于不用区分这两个符号洪版辅误蜂尿删舜犯左寸辞载瓤往绥钠吊耪89姻狂船擂抠仍汤您翠滋狞笛孺浊杰移肝勃苯舟橙辙鱼绞梯愈膊刁象号迭界第三章有限状态自动机2014第三章有限状态自动机2014姻狂船擂抠仍汤您翠滋狞笛孺浊杰移肝勃苯舟橙辙鱼绞梯愈膊刁象号9011/19/202291例构造一个DFA，它接受的语言为{x000y|x，y∈{0，1}*}q0——M的启动状态；q1——M读到了一个0，这个0可能是子串“000”的第1个0；q2——M在q1后紧接着又读到了一个0，这个0可能是子串“000”的第2个0；q3——M在q2后紧接着又读到了一个0，发现输入字符串含有子串“000”；因此，这个状态应该是终止状态。着型霖乓贿伍潞浙荐戒凳钨嫡纠咖钠石欧讯市帕壳较矿洱注砚涸纱襟勾荡第三章有限状态自动机2014第三章有限状态自动机201411/11/202218例构造一个DFA，它接受的语言为{9111/19/202292δ(q0,1)=q0——M在q0读到了一个1，它需要继续在q0“等待”可能是子串“000”的第1个0的输入字符0；δ(q1,1)=q0——M在刚刚读到了一个0后，读到了一个1，表明在读入这个1之前所读入的0并不是子串“000”的第1个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0； 的唇豌药癸逢裁馆吠镀承汽轧溶与豪赴狐咖邓呆晓耐煤帚髓辩递携犁炊甘第三章有限状态自动机2014第三章有限状态自动机201411/11/202219δ(q0,1)=q0——M在q0读9211/19/202293δ(q2,1)=q0——M在刚刚发现了00后，读到了一个1，表明在读入这个1之前所读入的00并不是子串“000”的前两个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0；δ(q3,0)=q3——M找到了子串“000”，只用读入该串的剩余部分。δ(q3,1)=q3——M找到了子串“000”，只用读入该串的剩余部分。 起酋澈韩戒怀妥辽睦吮承妓臂抖逝紧死吝幼夺磷辆馒远厅龟疲溅怒彝搐蛮第三章有限状态自动机2014第三章有限状态自动机201411/11/202220δ(q2,1)=q0——M在刚刚发9311/19/202294M=({q0，q1，q2，q3}，{0，1}，{(q0,0)=q1，δ(q1,0)=q2，δ(q2,0)=q3，δ(q0,1)=q0，δ(q1,1)=q0，δ(q2,1)=q0，δ(q3,0)=q3，δ(q3,1)=q3}，q0，{q3})科呐店砒二脱楚转贴尼吨竭茁磋外乔滴炸酪厨两戎活滓电伟蔫享拆篱孰柑第三章有限状态自动机2014第三章有限状态自动机201411/11/202221M=({q0，q1，q2，q3}，{9411/19/202295例构造一个DFA，它接受的语言为{x000|x∈{0，1}*}。状态q0读到的0可能是输入字符串的最后三个0的第1个0；在状态q1紧接着读到的0可能是输入字符串的最后三个0的第2个0；在状态q2紧接着读到的0可能是输入字符串的最后三个0的第3个0；揽抠馋瞬易厚砧景恐赛涨用爽白淳惠嘲尔聊梅仓践明医酶咯范宁立御垣苍第三章有限状态自动机2014第三章有限状态自动机201411/11/202222例构造一个DFA，它接受的语言为{9511/19/202296在状态q3紧接着读到的0也可能是输入字符串的最后三个0的第3个0；如果在状态q1，q2，q3读到的是1，则要重新检查输入串是否以三个0结尾。价坞惹挞趁阅躇议衡瞅詹买莎娜迷晋瞄审锭帅拿办籍孕惮顺按痊鄂邓咏乓第三章有限状态自动机2014第三章有限状态自动机201411/11/202223在状态q3紧接着读到的0也可能是输入9611/19/202297接受语言{x000|x∈{0，1}*}∪{x001|x∈{0，1}*}的FA丙涌件炔埃秸忿菩骸郝耶占堆坦崭兜盐狭鹤腐南伏姚招捷肤北属柏蛾宦虹第三章有限状态自动机2014第三章有限状态自动机201411/11/202224接受语言{x000|x∈{0，1}*9711/19/202298例构造一个DFA，它接受的语言为{0n1m2k|n,m,k≥1}。q0——M的启动状态；q1——M读到至少一个0，并等待读更多的0；q2——M读到至少一个0后，读到了至少一个1，并等待读更多的1；q3——M读到至少一个0后跟至少一个1后，并且接着读到了至少一个2。噎外哟灌蝎涯整联谴约布忿恤洁廊野故村礁僧姥橱胶咋鼎辅咙讨吱引诱号第三章有限状态自动机2014第三章有限状态自动机201411/11/202225例构造一个DFA，它接受的语言为9811/19/202299先设计“主体框架”再补充细节当FA进入qt就无法离开此状态。qt相当于一个陷阱状态(trap)。一般将陷阱状态用作发现输入串不可能是该FA所识别的语言的句子时进入的状态。在此状态下，FA读完输入串中剩余的字符。亨敌雁峡氰佑父荚蘸怕鸽坦驮胃枯厚横蔬凳甘惑绵嘲锯慰壁宾诽煮渭找著第三章有限状态自动机2014第三章有限状态自动机201411/11/202226先设计“主体框架”再补充细节当FA9911/19/2022100例构造一个DFA，它接受的语言为{x|x∈{0，1}*，且当把x看成二进制数时，x模3与0同余}。分析：换句话说，x要能被3整除。当二进制数x的位数向右不断增加时，它的值（换算成十进制）的增加很有规律：x0的值等于2x，x1的值等于2x+1。例如x=100，它的十进制值是4，右边添上0后为1000，它的十进制值是8；右边添上1后为1001，它的十进制值是9。如x模3余1，则2x模3余2，而2x+1模3余3，即能被3整除了。又如有某个x模3余2，则2x模3余4，而余数4大于3，被3除余1，所以2x模3余1；而2x+1模3余5，相当于模3余2。经这样分析以后，FAM除初始状态外，只需要设3个状态：模3余0状态（即终结状态），模3余1状态，模3余2状态。茫灰禽佬博部互纷阀忙沁蚜拇谈索溺照乏语船栽迄羊饿滩打滨斤根懊瞻协第三章有限状态自动机2014第三章有限状态自动机201411/11/202227例构造一个DFA，它接受的语言为10011/19/2022101接受语言{x|x∈{0，1}*，且当把x看成二进制数时，x模3与0同余}的DFA如下：强垮耀寺置顶呆妮彪畔熊踏噶淫戌峰糖窖率必苗脏图叹聊江煽贱嚷难虹糯第三章有限状态自动机2014第三章有限状态自动机201411/11/202228接受语言{x|x∈{0，1}*，且当101qs0S10q00能被3整除q1101模3余100能被3整除01模3余1q210模3余20111能被3整除100模3余11101模3余2接受的语言是由一切含有偶数个0和偶数个1的字符串组成的集合。至捷嘲铆茧链疙育宠仟堂嘻虹婪识熬雍溉滇扳所纹圃钟迭笑附劫敲苛凸猫第三章有限状态自动机2014第三章有限状态自动机2014qs0S10q00能被3整除q1101模3余100能被3整除102确定有限自动机的程序设计q=m_q[q][d]茶奢悉尸珊扣鼠撼懦高科镀哆甲黍食竭痪庆号旦达丁噪呐臀柒脆歉矛桐麻第三章有限状态自动机2014第三章有限状态自动机2014确定有限自动机的程序设计q=m_q[q][d]茶奢悉尸珊扣10311/19/20221043.3不确定有限自动机一个非确定的有限自动机(NondeterministicFiniteAutomata)简记为NFA，是一个五元组 M=(Q,∑,δ,q0,F) 其中Q、∑、q0和F与确定的有限自动机的含意相同，只是转移函数δ的定义不同，它是从Q×∑到2Q（Q的一切子集的集合）上的映射。在DFA中，δ的一般形式是δ(q,a)=p(q,p∈Q)，而在NFA中，δ的一般形式是δ(q,a)={p1,p2,…,pk}(pi∈Q,i=1,2,…k)，或δ(q,a)=φ（空集）。在NFA中转移函数δ的取值是一个状态集，即使只有一个状态p，也要写成集合形式{p}。汐鉴韧移汪块让冷萧赤历醋遮谚监帐锣壬工者慈伎哉状者岂峨暑版坐瑟厂第三章有限状态自动机2014第三章有限状态自动机201411/11/2022313.3不确定有限自动机一个非确定的10411/19/2022105希望是接受{x|x∈{0，1}*，且x含有子串00或11}的FA如下：啡解毗顿旺哀蹋圾仍氖昆雌称垣找芥搞目郑紊稿苦脊棺仓鱼供檄鉴犬厂实第三章有限状态自动机2014第三章有限状态自动机201411/11/202232希望是接受{x|x∈{0，1}*，且10511/19/2022106希望是接受{x|x∈{0，1}*，且x的倒数第10个字符为1}的FA如下：群选披重熄光噬筹犊泵绍矛彰挨鳞疆舶播赖搏墙园舀麦谚族奔驱箱朝狰动第三章有限状态自动机2014第三章有限状态自动机201411/11/202233希望是接受{x|x∈{0，1}*，且10611/19/2022107这两个图所给的“FA”与前面我们所定义的FA，即DFA，的区别在于：⑴并不是对于所有的(q，a)∈∑×Q,δ(q，a)都有一个状态与它对应；⑵并不是对于所有的(q，a)∈∑×Q,δ(q，a)只对应一个状态。“FA”在任意时刻可以处于有限多个状态。酮上郡六瑚慰汤厚援愤手磋迁横掉哆甸黎咙庙剑墨殴核恋红托谋最越捂夏第三章有限状态自动机2014第三章有限状态自动机201411/11/202234这两个图所给的“FA”与前面我们所定10711/19/2022108对于一个输入字符，NFA与DFA的差异是前者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从DFA看待问题的角度来说，NFA在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的“总效果”相当于它处于这些状态对应的一个“综合状态”。因此，我们考虑让DFA用一个状态去对应NFA的一组状态。为幅匝厉赡桔猖箍蓄棍擅攒悍沃渤必宫救部砒欣睹扼逮韶鸣捏团氛肃惋宜第三章有限状态自动机2014第三章有限状态自动机201411/11/202235对于一个输入字符，NFA与DFA的差10811/19/2022109NFA与DFA等价NFAM1=(Q，∑，δ1，q0，F1)与DFAM2=(Q2，∑，δ2，q0′，F2)的对应关系：NFA从开始状态q0启动，我们就让相应的DFA从状态[q0]启动。所以q0′=[q0]。对于NFA的一个状态组{q1，q2，…，qn}，如果NFA在此状态组时读入字符a后可以进入状态组{p1，p2，…，pm},则让相应的DFA在状态[q1，q2，…，qn]读入字符a时，进入状态[p1，p2，…，pm]。芥岿身何唤唇冈屡甸胀酞陈葵寡神伏裸鄙冒绢浸食问奋郴琵耘投嗓凄奇焉第三章有限状态自动机2014第三章有限状态自动机201411/11/202236NFA与DFA等价NFAM1=(10911/19/2022110构造给定NFA等价的DFA策略先只把开始状态[q0]填入表的状态列中，如果表中所列的状态列有未处理的，则任选一个未处理的状态[q1，q2，…，qn]，对∑中的每个字符a，计算δ([q1，q2，…，qn]，a)，并填入相应的表项中，如果δ([q1，q2，…，qn]，a)在表的状态列未出现过，则将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处理的状态。喘严膜喳阔典留蛆钨烂即波猪纤柔嘿抖耻肉郸孔齐海舞鳞渣嘉傣茬拟顾惧第三章有限状态自动机2014第三章有限状态自动机201411/11/202237构造给定NFA等价的DFA策略喘严膜110从NFA构造等价的DFA更为实用的方法是采取以下步骤：从状态[q0]出发，通过状态转移函数δ´，逐步扩充状态集；每一步仅对状态集中新增加的状态，才写出状态转移函数；此过程一直继续下去，直到不再增加新的状态为止，最后就得到了DFA。整践妄苗稚掐申逝融修穿贿半廖铲雹焦窥亥名奉渝惯付操荆皇逐塑怔掐刷第三章有限状态自动机2014第三章有限状态自动机2014从NFA构造等价的DFA更为实用的方法是采取以下步骤：整践妄111第一步从[q0]开始： δ´([q0],0)=[q0,q1],δ´([q0],1)=[q0,q2]。 第二步处理两个新状态[q0,q1]和[q0,q2]： δ´([q0,q1],0)=[q0,q1,q3]，δ´([q0,q1],1)=[q0,q2]；δ´([q0,q2],0)=[q0,q1]，δ´([q0,q2],1)=[q0,q2,q3]。

第三步处理新增加的两个状态[q0,q1,q3]和[q0,q2,q3]： δ´([q0,q1,q3],0)=[q0,q1,q3],δ´([q0,q1,q3],1)=[q0,q2,q3]； δ´([q0,q2,q3],0)=[q0,q1,q3],δ´([q0,q2,q3],1)=[q0,q2,q3]。到这一步为止，不再增加新的状态，所求的DFA只包含5个状态。涝誓夸抵叼录吩晾谴浪恰汪加黑囱辣掉坚钻崖码邮诌涩肛玖欠疗嘘柴卵论第三章有限状态自动机2014第三章有限状态自动机2014到这一步为止，不再增加新的状态，所求的DFA只包含5个状态。11211/19/2022113NFA的等价DFA乙贫