有限状态自动机

《有限状态自动机》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/8/241第3章有限状态自动机主要内容确定的有限状态自动机(DFA)不确定的有限状态自动机(NFA)带空移动的有限状态自动机(ε-NFA)带输出的有限状态自动机2021/8/242有限状态系统实例指针式钟表共有12*60*60个状态，每过一秒，钟表就从一种状态到另一种状态。围棋共有3361个状态，每走一步棋就从一个状态到另一个状态。电视开电视关打开关闭2021/8/243有限状态系统——淘宝网上购物顾客、店家和支付宝网三方之间的交互限于以下几种事件：1、顾客告诉店家购买某种物品，决定预付款购物。

2、并将钱款转入支付宝。2、顾客决定取消预付款。顾客通知支付宝，把购物这笔钱保留在自己的银行帐号上。3、店家送货给顾客。4、顾客收到货后（1）确认付款。通知支付宝将钱款划拨到店家帐号，转到（5）（2）退货。把购物这笔钱保留在自己的银行帐号上，结束。（3）换货。寄回店家，店家重送货给顾客。5、支付宝将这笔钱转帐。把顾客购物这笔钱划拨给店家的帐号。以上的事件以及事件间在一定条件下转化的情况，可以表示成有限状态系统，每个状态表示某一方所处的局面。选物品预付款已购物送货已收货换货更换物品选物品预付款已购物确认付款认可

3、物品退货不认可物品换货取消选物品已购物确认付款认可物品转帐交易结束不认可物品取消取消2021/8/2453.1语言的识别推导和归约中的回溯问题将对系统的效率产生极大的影响SaA

4、aBAaA

5、cBaB

6、d系统识别语言{anc

7、n≥1}∪{and

8、n≥1}的字符串过程中状态的变化图示如上2021/8/246识别系统(模型)⑴系统有有限个状态，不同状态代表不同的规定任务。⑵输入字符串中出现的字符构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。⑶系统在任何一个状态下，从输入字符串中读入字符后，

9、可转到新的状态（或状态不变）。下一次再读时，会读入下一个字符。2021/8/247⑷系统中有一个开始状态，系统在这个状态下开始进行某个给定句子的处理。⑸系统中有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。2021/8/248相应的物理模型一个右端无穷的输入带。一个有限状态控制器(finitestatecontrol,FSC)。一个读头。系统的每一个动作由三个节拍构成：读入读头正注视的字符；

10、根据当前状态和读入的字符改变有限控制器的状态；将读头向右移动一格。2021/8/2493.2有限状态自动机有限状态自动机(finiteautomaton,FA)是一个五元组：M=(Q，∑，q0，δ，F)Q——状态的非空有限集合。q∈Q，q为M的一个状态。∑——输入字母表。输入字符串都是∑上的字符串。q0——q0∈Q，是M的开始状态（初始状态或者启动状态）。2021/8/2410δ——状态转移函数(转换函数或移动函数)，δ：Q×∑Q，对(q，a)∈Q×∑，δ(q，a)=p表示：M在状态q读入字符a，将

11、状态变成p，并将读头指向输入字符串的下一个字符。F——FQ，是M的终止状态集合。q∈F，q称M的终止状态（接受状态）。状态转移图状态转换图2021/8/2411例有限状态自动机M1=({q0，q1，q2}，{0}，δ1，q0，{q2})其中：δ1(q0,0)=q1δ1(q1,0)=q2，δ1(q2,0)=q1q00q1S0q20识别{(00)n

12、n>=1}有限自动机的表示（1）转移图表示法（2）矩阵表示法符号状态0q0（初始）q1q1q2q2（终止）q12021/8/2414确定的有限状态自动机对于任

13、意的q∈Q，a∈∑，δ(q，a)均有确定的值，这种FA称为确定的有限状态自动机(deterministicfiniteautomaton，DFA)M接受(识别)的语言对于x∈∑*如果δ’(q0，x)∈F，则称x被M接受。L(M)={x

14、x∈∑*且δ(q0，x)∈F}称为由M接受(识别)的语言δ：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)=δ’(

15、q,a)=δ(δ’(q,),a)=δ(q,a)对于δ(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不用区分这两个符号2021/8/2418例构造一个DFA，它接受的语言为{x000y

16、x，