有限自动机理论3章有限状态自动机.ppt
《有限自动机理论3章有限状态自动机.ppt》由会员分享,可在线阅读,更多相关《有限自动机理论3章有限状态自动机.ppt(373页珍藏版)》请在三一文库上搜索。
1、第三章,有限状态自动机,定义语言,可以从两个方面进行: )从产生语言的角度; )从接收(或识别)语言的角度。,形式语言研究内容,产生一个语言: 1)定义语言中的基本句子; 2)根据其余句子的形成规则,产生出该语言所包含的所有句子。,有限自动机研究内容,使用某种自动机模型来接收字符串 接收的所有字符串形成的集合,也是一个语言,统一的理论,形式语言与自动机作为统一的理论,实际上包括3个方面的内容: 1) 形式语言理论(文法产生语言) 2) 自动机理论(自动机接收语言) 3) 形式语言与自动机的等价性理论 (文法与自动机等价转换),有限状态自动机 FA (Finite state Automaton
2、),FA是为研究 有限存储的计算过程 正则语言 而抽象出的一种计算模型。,两类有限状态自动机,接收器 判断是否接收输入串; 转换器 对给定输入串产生输出。,FA还可以分为,确定的FA-DFA Deterministic Finite state Automaton 非确定FA- NFA Non-deterministic Finite state Automaton,等价性,有限状态自动机接收的语言称为有限状态语言-FSL 从产生语言角度而言, FSL就是右线性语言-RLL 从(正则)运算角度而言, FSL就是正则语言-RL,有限状态自动机除在理论上的研究价值外 还在数字电路设计、编译技术(词
3、法分析)、系统辅助软件(文本编辑程序)、漏洞检测、交通控制等应用领域得到广泛应用,3.1 有限状态自动机,有限状态自动机是具有离散输入和离散输出的一种数学模型。 有限状态自动机是否接收串w 有限状态自动机是否接收语言L,有限状态自动机物理模型,a1,a2,a3,aj,an,an+1,FSC,一个输入存储带(输入带),带被分解为单元,每个单元存放一个输入符号(字母表上的符号)。 整个输入串从带的左端点开始存放,而带的右端可以无限扩充;,一个有穷状态控制器(FSC) 该控制器的状态只能是有限多个 FSC通过读头读取当前带上单元的字符。,初始时,读头对应带的最左单元,每读取一个字符,读头向右自动移动
4、一个单元。 读头不允许向左移动。,有限状态自动机的一个动作为: 读头读取带上当前单元的字符 FSC根据当前FSC的状态和读取的字符,进行状态改变; 将读头向右移动一个单元。,有限态自动机的动作简化为: FSC根据 当前状态 和 当前读取的带上字符 进行状态改变。,定义3-1 有限状态自动机FA,FA是一个五元式 FA=(Q,q0,F) Q是有限状态的集合 是字母表,即输入带上的字符集合,q0Q是开始状态 FQ是接收状态(终止状态)集合,是QQ的状态转换函数 即(q,x)= q 代表自动机在状态q时,扫描字符x后到达状态q,有限状态自动机的状态转换函数的个数应该为 |Q|*| 对于Q中的每个状态
5、,需要定义对应每个字母的状态转换。,DFA,这种有限状态自动机为确定的有限状态自动机DFA。,例3-1,定义DFA为: DFA=(q0,q1,0,1,q0,q0) 其中:,的表示:函数形式,(q0,0)=q1 (q0,1)=q1 (q1,0)= q1 (q1,1)= q0,的表示:状态矩阵,Q ,0,q0,1,q1,q1,q1,q1,q0,的表示:状态图形式,状态图是一个有向、有循环的图 一个节点表示一个状态; 若有(q,x)= q,则 状态q到状态q有一条有向边,并用字母x作标记。,的表示,指向的状态是开始状态 两个圆圈代表接收状态;,的表示:状态图,q1,1,0,1,0,q0,用状态图表示
6、一个DFA 有向边的数目就是状态转换函数的个数。,默认,(q,)=q 不是状态转换函数,3.2 有限状态自动机接收语言,对于DFA,给定串w=x1x2xn 初始时, DFA处于开始状态q0 从左到右逐个字符地扫描串w,在(q0,x1)= q1的作用下 DFA处于状态q1 在(q1,x2)=q2的的作用下 DFA处于状态q2 ,当将串w扫描结束后, 若DFA处于某一个接收状态, 则有限状态自动机能够接收串w,对于可接收串,DFA从开始状态开始,在扫描串的过程中, 状态逐个地变化,串扫描结束后, 到达某个接收状态。,对于不可接收串,DFA从开始状态开始,在扫描串的过程中, 状态逐个地变化,串扫描结
7、束后, 处于非接收状态。,对于字母表上的DFA 能够接收的所有串的集合,就是 DFA能接收的语言,记为L(DFA) 也称为有限状态语言(FSL),思考,如何形式化定义L(DFA)?,定义3-4 扩展的状态转换函数,给定DFA,扩展的状态转换函数 *:Q*Q 即 *(q,w)=q 即DFA在一个状态q时,扫描串w后到达唯一确定的状态q,递归扩展的状态转换函数,*(q,)=q *(q,a)=(q,a) 其中a,对于串w=a(+) *(q, w) =*(q,a) =(*(q,),a),或者,对于串w= a *(q,w) =*(q,a) =*(q,a),),定义3-6 DFA接收的语言,DFA=(Q,
8、q0,F)接收的语言 L(DFA)=w|*(q0,w)F,思考,如何描述 在某个时刻,DFA所处的情况?,定义3-7 DFA的瞬时描述(格局),格局是一个二元式:qy q是DFA当前状态 y是输入带上还没有被扫描到的串 读头将扫描y串的第1个字母,在扫描串的过程中,格局在发生转换(改变) 格局的(一次)转换的原因是由于函数的(一次)作用,如果当前格局为:qar 有函数:(q,a)= q 则下一格局为: qr 格局的转换可以记为: qar = qr,DFA的特殊格局,初始格局为: q0w 接收格局为: qf 其中,qf是某个接收状态,使用=*代表格局的任意次转换 使用=+代表格局的多次转换,可以
9、使用格局的转换方式定义FSL,DFA接收的语言 L(DFA)= w|q0w=*qf;w*且qfF,定义3-8 DFA停机,DFA将输入串扫描结束时 (自动)停机 这是DFA唯一的停机情况,注意1:,DFA将输入串扫描结束停机时, 如果DFA处于某一个接收状态, 则表示接收整个输入串; 反之,则表示不接收整个输入串;,注意2:,对于状态q,如果不能接收字母a 则将状态转换到一个特殊的状态:陷阱状态qt,陷阱状态qt不能够改变为其他状态 即 对于a (qt ,a)=qt qt不能够接收任意字母,构造DFA,分别接收语言,、0、01、 0*、 0+ (0+1)*、(0+1)+ 01*0 、1 *00
10、(0+1) * (0+1) *00(0+1) * 0(0+1) *1 0(0+1) *0+1(0+1)*1 ,定理3-1,每个FSL都是一个右线性语言 分析: 已知 接收FSL的DFA 需要 构造RLG,使得 L(RLG)=FSL,等价思路,DFA最重要的部分是状态转换函数 文法最重要的部分是产生式 考虑状态转换函数和产生式的等价作用: 将状态转换函数改造为产生式,等价思路,状态转换函数和产生式的等价作用 (q, a)=q AaB 接收a 产生a 状态变化 非终结符号变化 结论:DFA状态等价于文法非终结符 状态转换函数等价于产生式,构造文法的基本思路:,将的DFA的状态当作是RLG的非终结符
11、(开始状态就是开始符号) 对于某个句子: DFA通过状态的改变,逐步(自左向右)接收句子的每个字母; RLG通过非终结符号的改变,逐步(自左向右)产生句子的每个字母。,思考,DFA的接收状态的作用,证明,假设L是字母表上的FSL,则 L=L(DFA),DFA=(Q,q0,F) 构造右线性文法G=(,Q,q0,P) 其中P为:,qaq|(q,a)=q U qa|(q,a)F 特别,若q0是接收状态,则 q0,对于句子w=x1x2xn,DFA: 则文法有 (q0, x1)=q1 q0x1q1 (q1, x2)=q2 q1x2q2 (qn-2,xn-1)=qn-1 qn-2xn-1qn-1 (qn-
12、1, xn)=qn qn-1xnqn 或 qn-1xn,所以,DFA 文法 *(q,)=q q=*q *(q0, w)F q0=*w 注意: 陷进状态在文法中是无用非终结符,例3-2 DFA与文法的转换,FSL=(0,1)1*0* 接收该语言的DFA为:,q1,1,0,0,1,q0,构造正则文法产生该语言: q00q1|1q1| q10q0|1q1| 0,定理3-2,FSL对补运算封闭,证明:,设L1是上的FSL,且L1=L(DFA1), DFA1=(Q,q0,F),构造 DFA2=(Q,q0,Q) DFA2接收的语言是 L1的对应的全集,即*,构造 DFA3=(Q,q0,Q-F) L3=L(
13、DFA3) L3接收的语言是L1(关于*)的补 L3也是FSL语言。,注意,此时的DFA1的函数的个数为 |Q|*|,基本的等价替换,对于状态转换图,有基本的等价替换 变换为,0,1,1,3.3 DFA接收语言的例子,构造DFA,接收语言 L=ab,基本结构(接收基本句子),q1,a,b,q0,q2,增加陷阱状态后的DFA,q1,a,b,q0,qt,b,a,a, b,a, b,q2,思考1,如果将该DFA的所有状态都设置为接收状态(包括陷阱状态), 接收的语言是?,思考2,如果将该自动机的接收状态和非接收状态对调 接收的语言是?,例3-4构造DFA,接收语言L=x000y|x,y0,1*,分析
14、,该语言的特点是 语言中的每个串都包含连续的3个0(即每个串都包含子串000),因此,对于任何输入串,有限状态自动机的任务就是要检查该输入串中是否存在子串000, 一旦发现输入串包含有000,则表示整个输入串是句子。,因此,在确认输入串包含000后, 就可以逐一地读入000后面的全部字符,并接收该输入串。,思考,问题的关键是? 如何发现子串000。,由于字符是逐一读入的,当从输入串中读入一个0时, 它有可能是000的第1个0, 需要记住已经出现过一个0;,如果紧接着读入的是字符1, 则刚读入的0就不是000的第1个0 需要重新寻找000子串的第1个0;,如果紧接着读入的还是0,它有可能是000
15、的第2个0, 也需要记住这个0, 继续读入字符,若是0,则发现000 否则,需要重新寻找000。,初始状态:q0 接收0,到达状态q1 接收00 ,到达状态q2 接收000,到达状态q3,因此,基本的状态转移函数为: (q0,0)=q1 (q1,0)=q2 (q2,0)=q3 用于接收基本句子000,接收000的状态图,q0,0,0,0,q1,q2,q3,其他状态转移函数为: (q0,1)=q0 期待0的出现 (q1,1)=q0 重新寻找000 (q2,1)=q0 重新寻找000 (q3,0)=q3 扫描后续字符 (q3,1)=q3 扫描后续字符,状态转移图,q0,0,1,1,1,0,0,0,
16、1,q1,q2,q3,思考,如果需要接收语言 L 如何修改有限状态自动机? 思路:考虑开始状态的作用,思考:如果,DFA的开始状态只负责接收输入串的第一个字母; 文法的开始符号只负责串的推导的开始; 优点是?,状态图为,例3-5构造DFA,接收语言 L=x001y|x,y0,1*,分析:,对于任何输入串,DFA的任务就是要检查该输入串中是否存在001,初始状态:q0 q1 已接收0 q2 已接收00 q3 已接收001,q2,q1,q0,状态转移图,0,1,q3,1,0,1,0,1,0,例3-6 构造DFA,接收语言L=x000|x0,1*,q2,q3,q1,q0,0,1,1,1,0,0,0,
17、1,例3-7构造DFA,接收语言L=x000x001 其中,x0,1*,q2,q1,q0,0,1,q3,1,0,0,0,1,q4,1,0,1,例3-8构造DFA,接收语言L=02k+3m|m,k=0,实际上: 2k+3m 可以表示任意的非负整数(除1外) 该语言为0*-0,状态转移图,0,0,0,q1,q2,q0,思考:构造DFA,接收语言L=02k+3m|m,k0,例3-9构造DFA,接收0,1上的语言,该语言的 每个句子以0开头,以1结尾。,状态转移图,0,1,0,q1,q2,1,0,qt,0,1,1,q0,例3-10 构造DFA,接收0,1上的语言,该语言的每个字符串 不包含00子串(语
18、言允许 ),0,0,0,1,qt,q1,q0,q2,1,0,1,1,或,0,0,0,1,qt,q1,q0,1,1,构造DFA,接收0,1上的语言, 该语言的每个字符串不包含00 (语言不允许 ),例3-11构造DFA,接收0,1,2上的语言, 该语言的每个字符串代表的数字能整除3。,分析,如果一个十进制整数的所有位的数字的和能够整除3,那么, 这个十进制整数就能够整除3;,一个十进制整数除以3,余数只能是1、2和0;,将整数当作一个字符串,从左到右逐一地读入; 使用3个状态分别代表已读入的数字的和除以3的余数情况: (即读入的整数对3的余数情况),q0:已读入的整数除以3,余数为0 q1:已读
19、入的整数除以3,余数为1 q2:已读入的整数除以3,余数为2,思考,已知 qi(i =0,1,2),k=0,1,2 应该如何确定 j?,qi,qj,k,扫描子串w后,处于某个状态qi, 读入当前数字, 状态转换情况为,q0,在此状态读入0,引导DFA到达下一状态的输入串为w0, w0的各位数字和除以3,余数为0。所以, DFA在q0状态读入0,应该继续保持q0状态;,q0,在此状态读入1,引导DFA到达下一状态的输入串为w1,w1的各位数字和除以3,余数为1。 所以, DFA在q0状态读入1,应该到达q1状态;,q0,在此状态读入2,引导DFA到达下一状态的输入串为w2,w2的各位数字和除以3
20、,余数为2。 所以, DFA在q0状态读入2,应该到达q2状态; ,存在的问题,接收的串包括以0开始的数字串; 还能够接收空串,思考,如何进行改进,使得 接收的串不能以0开始, 不能接收空串。,定义3-9 set集合,对于状态q,能将DFA从q0转换到q状态的所有字符串的集合为: set(q)=w|w*,*(q0,w)=q,则有限状态自动机DFA接收的语言可以定义为: L(DFA)= set(q) 其中: qF,按状态进行划分,对于DFA,可以定义关系R 若 x,y* ,qQ 则 xRy 当且仅当 xset(q),yset(q) 即R=(x,y)|xset(q),yset(q) ;qQ 是*上
21、的二元关系,该关系是集合*上的一个等价关系,利用该关系, 可以将*划分为不多于|Q|个的等价类。,DFA可以按照语言的特点给出字母表*的一个划分,这种划分相当于*上的一个等价分类。 DFA每个状态对应着一个等价类,利用一个状态去表示一个等价类是构造DFA的一条有效思路。,例3-12构造DFA,接收,0,1,2,4,5,6,7,8,9上的语言, 该语言的每个字符串代表的数字能整除3。,仍然只使用3个状态分别代表已经读入的整数字的和除以3的不同的余数的情况:,状态与对应的等价类,q0:余数为0的输入串的等价类 q1:余数为1的输入串的等价类 q2:余数为2的输入串的等价类,例3-13构造DFA,接
22、收,0,1上的语言,该语言的每个字符串挡成二进制数时, 代表的数字能整除3。,DFA的每个状态对应一个等价类 利用一个状态去表示一个等价类 除以3的余数只能为0、1和2,q0:余数为0的输入串的等价类; q1:余数为1的输入串的等价类; q2:余数为2的输入串的等价类;,不能接收空串,所以, 还需要一个开始状态qS,人们习惯使用十进制数,w=x1x2x3xn (x1x2x3xn)2=(x1*2n-1+ x2*2n-2+ xn-1*2+xn)10 当串长度增加1时: (x1x2x3xnxn+1)2= (x1*2n+ x2*2n-1+ xn-1*22+ xn*2+xn+1)10 =(2*(w)10
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 有限 自动机 理论 状态
链接地址:https://www.31doc.com/p-3297708.html