有限自动机理论03章有限状态自动机

第三章有限状态自动机定义语言可以从两个方面进行：１）从产生语言的角度；２）从接收(或识别)语言的角度。形式语言研究内容产生一个语言:1)定义语言中的基本句子;2)根据其余句子的形成规则，产生出该语言所包含的所有句子。有限自动机研究内容使用某种自动机模型来接收字符串接收的所有字符串形成的集合，也是一个语言统一的理论形式语言与自动机作为统一的理论,实际上包括3个方面的内容:1)形式语言理论(文法产生语言)2)自动机理论(自动机接收语言)3)形式语言与自动机的等价性理论(文法与自动机等价转换)有限自动机分为3类有限状态自动机FA下推自动机PDA图灵机TM有限状态自动机FA(FinitestateAutomaton)FA是为研究有限存储的机制和正则语言而抽象出的一种模型。两类有限状态自动机接收器判断是否接收输入串；转换器对给定输入串产生输出。FA还可以分为确定的FA----DFADeterministicFinitestateAutomaton非确定FA----NFANon-deterministicFinitestateAutomaton等价性有限状态自动机接收的语言称为有限状态语言--FSL从产生语言角度而言，FSL就是右线性语言--RLL从(正则)运算角度而言，FSL就是正则语言--RL有限状态自动机除在理论上的研究价值外还在数字电路设计、编译技术(词法分析)、系统辅助软件(文本编辑程序)、漏洞检测、交通控制等应用领域得到广泛应用3.1有限状态自动机有限状态自动机是具有离散输入和离散输出的一种数学模型。有限状态自动机是否接收串w有限状态自动机是否接收语言L有限状态自动机物理模型a1a2a3…aj…anan+1…FSC一个输入存储带（输入带），带被分解为单元，每个单元存放一个输入符号(字母表上的符号)。整个输入串从带的左端点开始存放，而带的右端可以无限扩充；一个有穷状态控制器（FSC）该控制器的状态只能是有限多个FSC通过读头读取当前带上单元的字符。初始时，读头对应带的最左单元，每读取一个字符，读头向右自动移动一个单元。读头（暂时）不允许向左移动。有限状态自动机的一个动作为：读头读取带上当前单元的字符FSC根据当前FSC的状态和读取的字符，进行状态改变；将读头向右移动一个单元。有限态自动机的动作可以简化为：FSC根据当前状态和当前读取的带上字符进行状态改变。定义3-1有限状态自动机FAFA是一个五元式FA=(Q，∑，δ，q0，F)Q是有限状态的集合∑是字母表，即输入带上的字符集合q0∈Q是开始状态FQ是接收状态(终止状态)集合δ是Q×∑→Q的状态转换函数即δ(q，x)=q′代表FA在状态q时，扫描字符x后状态改变为q′（也称到达状态q′）有限状态自动机的状态转换函数的个数应该为|Q|*|∑|对于Q中的每个状态，需要定义对应∑每个字母的状态转换。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∑0q01q1q1q1q1q0δ的表示:状态图形式状态图是一个有向、有循环的图一个节点表示一个状态；若有δ(q，x)=q′，则状态q到状态q′有一条有向边，并用字母x作标记。δ的表示‘→’指向的状态是开始状态两个圆圈代表接收状态；δ的表示：状态图q11010q0用状态图表示一个DFA有向边的数目就是状态转换函数的个数。默认有δ(q,ε)=q但不是状态转换函数why?3.2有限状态自动机接收语言对于DFA，给定串w=x1x2…xn初始时，DFA处于开始状态q0从左到右逐个字符地扫描串w在δ(q0，x1)=q1的作用下DFA处于状态q1在δ(q1，x2)=q2的的作用下DFA处于状态q2…当将串w扫描结束后，若DFA处于某一个接收状态，则有限状态自动机能够接收串w对于可接收串DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，处于某个接收状态。对于不可接收串DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，处于某个非接收状态。对于字母表∑上的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-6DFA接收的语言DFA=(Q,∑,δ,q0，F)接收的语言L(DFA)={w|δ*(q0,w)∈F}思考如何描述在某个时刻，DFA所处的情况？定义3-7DFA的瞬时描述（格局）格局是一个二元式：qyq是DFA当前状态y是输入带上还没有被扫描到的串读头将扫描y串的第1个字母在扫描串的过程中，格局在发生转换(改变)格局的(一次)转换的原因是由于δ函数的(一次)作用如果当前格局为：qar有δ函数：δ(q，a)=q′则下一格局为：q′r格局的转换可以记为：qar=q′rDFA的特殊格局初始格局为：q0w接收格局为：qfε其中，qf是某个接收状态使用=*代表格局的任意次转换使用=+代表格局的多次转换可以使用格局的转换方式定义FSLDFA接收的语言L(DFA)={w|q0w=*qfε；w∈∑*且qf∈F}定义3-8DFA停机DFA将输入串扫描结束时(自动)停机这是DFA唯一的停机情况注意1：DFA将输入串扫描结束停机时，如果DFA处于某一个接收状态，则表示接收整个输入串；反之，则表示不接收整个输入串;注意2：对于状态q,如果不能接收字母a则将状态转换到一个特殊的状态：陷阱状态qt陷阱状态qt不能够改变为其他状态即对于a∈∑δ(qt，a)=qtqt不能够接收任意字母构造DFA，分别接收语言ε、0、01、0*、0+(0+1)*、(0+1)+01*0、1*00(0+1)*(0+1)*00(0+1)*0(0+1)*10(0+1)*0+1(0+1)*1…定理3-1每个FSL都是一个右线性语言分析：已知接收FSL的DFA需要构造RLG，使得L(RLG)=FSL等价思路DFA最重要的部分是状态转换函数文法最重要的部分是产生式状态转换函数和产生式是等价的可以将状态转换函数改造为产生式等价思路状态转换函数和产生式的等价作用δ(q,a)=q′A→aB接收a产生a状态变化非终结符号变化结论:DFA状态等价于文法非终结符状态转换函数等价于产生式构造文法的基本思路：将的DFA的状态当作是RLG的非终结符(开始状态就是开始符号)对于某个句子：DFA通过状态的改变，逐步（自左向右）接收句子的每个字母；RLG通过非终结符号的改变，逐步（自左向右）产生句子的每个字母。思考DFA的接收状态的作用证明假设L是字母表∑上的FSL，则L=L(DFA)DFA=（Q，∑，δ，q0，F）构造右线性文法G=(∑,Q,q0，P）其中P为：{q→aq′|δ(q，a)=q′}U{q→a|δ(q，a)∈F}特别，若q0是接收状态，则q0→ε对于句子w=x1x2…xnDFA：则文法有δ(q0,x1)=q1q0→x1q1δ(q1,x2)=q2q1→x2q2……δ(qn-2,xn-1)=qn-1qn-2→xn-1qn-1δ(qn-1,xn)=qnqn-1→xnqn或qn-1→xn所以DFA文法δ*(q，α)=q′q=*αq′δ*(q0，w)∈Fq0=*w注意：陷进状态在文法中是无用非终结符例3-2DFA与文法的转换FSL={(0,1)1*0}*接收该语言的DFA为：q11001q0构造正则文法产生该语言：q0→0q1|1q1|εq1→0q0|1q1|0定理3-2FSL对补运算封闭证明：设L1是∑上的FSL,且L1=L(DFA1)，DFA1=（Q，∑，δ，q0，F）构造DFA2=（Q，∑，δ，q0，Q）DFA2接收的语言是L1的对应的全集,即∑*构造DFA3=(Q，∑，δ，q0，Q-F)L3=L(DFA3)L3接收的语言是L1(关于∑*)的补L3也是FSL语言。注意此时的DFA1的δ函数的个数为|Q|*|∑|基本的等价替换对于状态转换图，有基本的等价替换变换为00,113.3DFA接收语言的例子构造DFA，接收语言L={ab}基本结构（接收基本句子）q1abq0q2增加陷阱状态后的DFAq1abq0qtbaa,ba,bq2思考1如果将该DFA的所有状态都设置为接收状态(包括陷阱状态)，接收的语言是？思考2如果将该自动机的接收状态和非接收状态对调接收的语言是？例3-4构造DFA接收语言L={x000y|x,y∈{0,1}*}分析该语言的特点是语言中的每个串都包含连续的3个0（即每个串都包含子串000）因此，对于任何输入串，有限状态自动机的任务就是要检查该输入串中是否存在子串000，一旦发现输入串包含有000，则表示整个输入串是句子。因此，在确认输入串包含000后，就可以逐一地读入000后面的全部字符，并接收该输入串。思考问题的关键是？如何发现子串000。由于字符是逐一读入的，当从输入串中读入一个0时，它有可能是000的第1个0，需要记住已经出现过一个0；如果紧接着读入的是字符1，则刚读入的0就不是000的第1个0需要重新寻找000子串的第1个0；如果紧接着读入的还是0，它有可能是000的第2个0，也需要记住这个0，继续读入字符，若是0，则发现000否则，需要重新寻找000。初始状态：q0接收0，到达状态q1接收00,到达状态q2接收000,到达状态q3因此，基本的状态转移函数为：δ(q0，0)=q1δ(q1，0)=q2δ(q2，0)=q3用于接收基本句子000接收000的状态图q0000q1q2q3其他状态转移函数为：δ(q0，1)=q0期待0的出现δ(q1，1)=q0重新寻找000δ(q2，1)=q0重新寻找000δ(q3，0)=q3扫描后续字符δ(q3，1)=q3扫描后续字符状态转移图q00111000,1q1q2q3思考如果需要接收语言L∪{ε}如何修改有限状态自动机?思路：考虑开始状态的作用思考:如果DFA的开始状态只负责接收输入串的第一个字母；文法的开始符号只负责串的推导的开始；优点是？状态图为10qs01000,1q1q2q3q011例3-5构造DFA接收语言L={x001y|x，y∈{0，1}*}分析：对于任何输入串，DFA的任务就是要检查该输入串中是否存在001初始状态：q0q1已接收0q2已接收00q3已接收001q2q1q0状态转移图01q31010,10例3-6构造DFA接收语言L={x000|x∈{0，1}*}q2q3q1q001110001例3-7构造DFA接收语言L={x000}∪{x001}其中，x∈{0，1}*q2q1q001q310001q4101例3-8构造DFA接收语言L={02k+3m|m,k=0}实际上：2k+3m可以表示任意的非负整数(除1外)该语言为0*-{0}状态转移图000q1q2q0思考：构造DFA接收语言L={02k+3m|m,k0}考查题1例3-9构造DFA接收{0，1}上的语言，该语言的每个句子以0开头，以1结尾。状态转移图010q1q210qt0,11q0例3-10构造DFA接收{0，1}上的语言，该语言的每个字符串不包含00子串(语言允许ε)000,1qtq1q0q21011或000,1qtq1q011构造DFA接收{0，1}上的语言，该语言的每个字符串不包含00（语言不允许ε）例3-11构造DFA接收{0，1，2}上的语言，该语言的每个字符串代表的数字能整除3。分析如果一个十进制整数的所有位的数字的和能够整