《有限自动机理论3章有限状态自动机.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论3章有限状态自动机.ppt（373页珍藏版）》请在三一办公上搜索。
1、第三章,有限状态自动机,定义语言,可以从两个方面进行：）从产生语言的角度；）从接收(或识别)语言的角度。,形式语言研究内容,产生一个语言:1)定义语言中的基本句子;2)根据其余句子的形成规则，产生出该语言所包含的所有句子。,有限自动机研究内容,使用某种自动机模型来接收字符串 接收的所有字符串形成的集合，也是一个语言,统一的理论,形式语言与自动机作为统一的理论,实际上包括3个方面的内容:1)形式语言理论(文法产生语言)2)自动机理论(自动机接收语言)3)形式语言与自动机的等价性理论(文法与自动机等价转换),有限状态自动机 FA(Finite state Automaton),FA是为研究 有限存
2、储的计算过程 正则语言而抽象出的一种计算模型。,两类有限状态自动机,接收器 判断是否接收输入串；转换器 对给定输入串产生输出。,FA还可以分为,确定的FA-DFA DeterministicFinite state Automaton 非确定FA-NFANon-deterministicFinite 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中的每个状态，需要定义对应每个字母的状态转换。,DFA,这种有限状态自动机为确
5、定的有限状态自动机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,用状态图表示一个DFA 有向边的数目就是状态转换函数的个数。,默认,(q,)=q不是状态转换函数,3.
6、2 有限状态自动机接收语言,对于DFA，给定串w=x1x2xn 初始时，DFA处于开始状态q0 从左到右逐个字符地扫描串w,在(q0，x1)=q1的作用下 DFA处于状态q1 在(q1，x2)=q2的的作用下 DFA处于状态q2,当将串w扫描结束后，若DFA处于某一个接收状态，则有限状态自动机能够接收串w,对于可接收串,DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，到达某个接收状态。,对于不可接收串,DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，处于非接收状态。,对于字母表上的DFA 能够接收的所有串的集合，就是DFA能接收的语言，记为L(DFA
7、)也称为有限状态语言（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,q0，F)接收的语言 L(DFA)=w|*(q0,w)F,思考,如何描述 在某个时刻，DFA所处的情况？,定义3-7 DFA的瞬时描述（格局
8、）,格局是一个二元式：qy q是DFA当前状态 y是输入带上还没有被扫描到的串 读头将扫描y串的第1个字母,在扫描串的过程中，格局在发生转换(改变)格局的(一次)转换的原因是由于函数的(一次)作用,如果当前格局为：qar 有函数：(q，a)=q 则下一格局为：qr 格局的转换可以记为：qar=qr,DFA的特殊格局,初始格局为：q0w接收格局为：qf其中，qf是某个接收状态,使用=*代表格局的任意次转换使用=+代表格局的多次转换,可以使用格局的转换方式定义FSL,DFA接收的语言 L(DFA)=w|q0w=*qf；w*且qfF,定义3-8 DFA停机,DFA将输入串扫描结束时(自动)停机这是D
9、FA唯一的停机情况,注意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(
10、RLG)=FSL,等价思路,DFA最重要的部分是状态转换函数文法最重要的部分是产生式 考虑状态转换函数和产生式的等价作用:将状态转换函数改造为产生式,等价思路,状态转换函数和产生式的等价作用(q,a)=q AaB 接收a 产生a 状态变化 非终结符号变化结论:DFA状态等价于文法非终结符 状态转换函数等价于产生式,构造文法的基本思路：,将的DFA的状态当作是RLG的非终结符(开始状态就是开始符号)对于某个句子：DFA通过状态的改变，逐步（自左向右）接收句子的每个字母；RLG通过非终结符号的改变，逐步（自左向右）产生句子的每个字母。,思考,DFA的接收状态的作用,证明,假设L是字母表上的FSL，
11、则 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 q0 x1q1(q1,x2)=q2 q1x2q2(qn-2,xn-1)=qn-1 qn-2xn-1qn-1(qn-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
12、,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(DFA3)L3接收的语言是L1(关于*)的补 L3也是FSL语言。,注意,此时的DFA1的函数的个数为|Q|*|,基本的等价替换,对于状态转换图，有基本的等价替换变换为,0,1,1,3.3 DFA接收语言的例子,构造DFA，接收语言 L=ab,基本结构（接收基本句子）,q
13、1,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*,分析,该语言的特点是 语言中的每个串都包含连续的3个0（即每个串都包含子串000）,因此，对于任何输入串，有限状态自动机的任务就是要检查该输入串中是否存在子串000，一旦发现输入串包含有000，则表示整个输入串是句子。,因此，在确认输入串包含000后，就可以逐一地读入000后面的全部字符
14、，并接收该输入串。,思考,问题的关键是？如何发现子串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的状态图
15、,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,1,q1,q2,q3,思考,如果需要接收语言 L 如何修改有限状态自动机?思路：考虑开始状态的作用,思考:如果,DFA的开始状态只负责接收输入串的第一个字母；文法的开始符号只负责串的推导的开始；优点是？,状态图为,例3-5构造DFA,接收语言 L=x001y|x，y0，1*,分析：,对于任何输入串，DFA的任务就是要检查该输入串
16、中是否存在001,初始状态：q0q1 已接收0q2 已接收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,1,例3-7构造DFA,接收语言L=x000 x001其中，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=
17、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子串(语言允许),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，那么，这个十进制整
18、数就能够整除3；,一个十进制整数除以3，余数只能是1、2和0；,将整数当作一个字符串，从左到右逐一地读入；使用3个状态分别代表已读入的数字的和除以3的余数情况：(即读入的整数对3的余数情况）,q0：已读入的整数除以3，余数为0q1：已读入的整数除以3，余数为1q2：已读入的整数除以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,在
19、此状态读入1，引导DFA到达下一状态的输入串为w1，w1的各位数字和除以3，余数为1。所以，DFA在q0状态读入1，应该到达q1状态；,q0,在此状态读入2，引导DFA到达下一状态的输入串为w2，w2的各位数字和除以3，余数为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
20、)其中：qF,按状态进行划分,对于DFA，可以定义关系R 若 x,y*，qQ 则 xRy 当且仅当 xset(q),yset(q)即R=(x,y)|xset(q),yset(q)；qQ 是*上的二元关系,该关系是集合*上的一个等价关系，利用该关系，可以将*划分为不多于|Q|个的等价类。,DFA可以按照语言的特点给出字母表*的一个划分，这种划分相当于*上的一个等价分类。DFA每个状态对应着一个等价类,利用一个状态去表示一个等价类是构造DFA的一条有效思路。,例3-12构造DFA,接收,0,1,2,4,5,6,7,8,9上的语言，该语言的每个字符串代表的数字能整除3。,仍然只使用3个状态分别代表已
21、经读入的整数字的和除以3的不同的余数的情况：,状态与对应的等价类,q0：余数为0的输入串的等价类q1：余数为1的输入串的等价类q2：余数为2的输入串的等价类,例3-13构造DFA,接收,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
22、*2+xn)10当串长度增加1时：(x1x2x3xnxn+1)2=(x1*2n+x2*2n-1+xn-1*22+xn*2+xn+1)10=(2*(w)10+xn+1)10,(w)10=3n+i(wx)10=(2*(w)10+x)10=6*n+2*i+x实际上 2*i+x 对3的余数就是wx对3的余数,设w是当前已经读入的输入串；qS：开始状态读入0时，进入状态q0读入1时，进入状态q1,q0,能引导DFA到达此状态的w除以3余数为0，因此(w)10=3n+0,q0,在此状态读入0，引导DFA到达下一状态的输入串为w0，则(w0)10=2(3n+0)+0=32n+0 表明w0也属于q0对应的等价
23、类。所以，DFA在q0状态读入0，应该继续保持q0状态；,q0,在此状态读入1，引导DFA到达下一状态的输入串为w1，则(w1)10=2(3n+0)+1=32n+1 表明w1属于q1对应的等价类。所以，DFA在q0状态读入1，应该到达q1状态；,q1,能引导DFA到达此状态的w除以3余数为1，因此(w)10=3n+1,q1,在此状态读入0，引导DFA到达下一状态的输入串为w0，则(w0)10=2(3n+1)+0=32n+2 表明w0属于q2对应的等价类。所以，DFA在q1状态读入0，应该到达q2状态；,q1,在此状态读入1，引导DFA到达下一状态的输入串为w1，则(w1)10=2(3n+1)+
24、1=32n+3 表明w1属于q0对应的等价类。所以，DFA在q1状态读入1，应该到达q0状态；,q2,能引导DFA到达此状态的w除以3余数为2，因此，(w)10=3n+2,q2,在此状态读入0，引导DFA到达下一状态的输入串为w0，则(w0)10=2(3n+2)+0=32n+4 表明w0属于q1对应的等价类。所以，DFA在q2状态读入0，应该到达q1状态；,q2,在此状态读入1，引导自动机到达下一状态的输入串为w1，则(w1)10=2(3n+2)+1=32n+5 表明w1属于q2对应的等价类。所以，自动机在q2状态读入1，继续保持q2状态；,状态图,例3-14构造DFA，接收,0，1上的语言，
25、该语言的每个字符串为二进制数时，代表的数字能被5整除。,分析：,对5的余数只能为0、1、2、3和4使用5个状态分别代表已经读入的数字除以5的不同的余数的等价类：qi：已经读入的数除以5，余数为i的输入串的等价类；其中 i=0,1,2,3,4不能接收空串，需要一个开始状态qS,例3-15构造DFA，接收,1,2,3上的语言，该语言的每个字符串挡成十进制数时，代表的数字能被4整除。,思考：构造DFA，接收,0，1,2，3，4，5，6，7，8，9上的语言，该语言的每个字符串挡成十进制数时，代表的数字能整除7。,总结：构造DFA，接收,=x1,x2,x3,xm上的语言 该语言的每个字符串挡成base进
26、制数时 代表的数字能整除N 或 代表的数字对N的余数为K,分析：,对N的余数只能为0、1、2、3、和N-1 使用N个状态分别代表已经读入的串（当作数）对N的不同的余数的等价类：,q0：余数为0的输入串的等价类；该类数十进制为N*n+0,q1：余数为1的输入串的等价类；该类数十进制为N*n+1q2：余数为2的输入串的等价类；该类数十进制为N*n+2,qN-1：余数为N-1的输入串的等价类；该类数十进制为N*n+N-1,注意,不能接收空串，还需要一个开始状态qS,qS,读入x时，进入对应状态qi,本质,已知qi(i=0，1，2，N-1)x=x1,x2,x3,xm 应该如何确定 j？,qi,qj,x
27、,qi,已经读入的数为w，对应余数为i的输入串的等价类；该类数十进制为N*n+i,当前读入的字符为x；则wx表示的十进制数为(wx)10=base*(w)10+x=base*（N*n+i）+x=N*base*n+base*i+x,该数对于N取余数就是base*i+x对于N的余数，若该余数为j，则相应的状态就应该从qi变换为qj,其中 i=0，1，2，N-1。x=x1,x2,x3,xm 0,1，base-1,例3-16构造DFA，接收,0，1上的语言 L=0n1m2k|n,m,k=1,该语言的串的特点是，0在最前面，1在中间，2在最后，0、1和2不能交叉，顺序也不能颠倒。0、1和2的个数都至少为
28、1个；需要4个状态：,q0：开始状态,等待接收第1个0q1：已经接收第1个0，负责接收可能的多个0，等待接收第1个1；q2：已经接收第1个1，负责接收可能的多个1，等待接收第1个2；,q3：已经接收第1个2，负责接收可能的多个2。,状态转移图(省略陷阱状态),q0,0,1,0,1,2,2,q1,q2,q3,思考1,补充陷阱状态及对应的状态函数。,思考2 DFA是否可以为(省略陷阱状态),q0,0,1,0,1,2,2,q1,q2,q3,.4 不确定的有限状态自动机,每个FSL都是右线性语言(定理3-1),问题,每个右线性语言是不是一个FSL？,例,接收语言aa，ab的FA,省略陷阱状态,q1,a
29、,b,q0,q2,a,a,q3,该自动机接收的语言L=aa，ab是右线性语言；但自动机不是DFA。,(q0，a)=q1，q2 即没有到达确定的惟一的状态。不确定的有限状态自动机-NFA,不确定的有限状态自动机,定义3-10 NFA是一个五元式，NFA=（Q，Q0，F）其中：Q 是一个有限状态的集合 是字母表,Q0 Q 是开始状态集合 F Q 是接收状态集合,是Q2Q的状态转换函数即(q，a)2Q NFA在状态q，扫描字母a后到达可能的下一状态集合。,NFA与DFA,NFA有一个可能的开始状态集合和可能的下一状态集合 其余的同DFA。,NFA与DFA的重要区别在于 转移函数的不同。(q，x)对应
30、的是状态集合Q的一个子集,FA处于状态q,DFA对每个字母只有惟一的状态转移NFA对某个字母可以有多个状态转移；NFA接收该字母时,从多个状态转移中可以 非确定地选择任意一个。,具体地,对于NFA，(q，a)Q(q，a)有3种可能(q，a)=(q，a)=q1(q，a)=q1，q2，qn,或,或,(q，a)仍是一个状态转换函数，只是其值域发生了改变。所有(q，a)对应的所有子集元素个数都为1时，NFA退化为DFA,NFA停机,NFA在两种情况下自动停机：将输入串扫描结束(q，a)=(即对应没有定义),或,在扫描一个串w时，NFA的状态发生转换，可能会有多种情况：可能在接收状态时终止；可能在非接收
31、状态时终止；也可能在中途停止（中止）。,若至少存在一条路径可以使NFA在扫描串w后到达接收状态 则串w能被NFA所接收。,对于字母表上的NFA，它能接收的所有串的集合，称为NFA能接收的语言。记为 L(NFA),问题,如何形式化定义L(NFA)?,定义 NFA扩展状态转换函数,给定NFA，扩展的状态转换函数*：2Q*2Q 为*(p，w)=Q 即NFA在状态集合p时，扫描串w后到达可能的的状态集合Q,NFA扩展状态转换函数,若p=q1，q2，qn*（p，）=p,a,*(p，a)=(q，a)|qp=(q1,a),(q2,a),(qn,a),对于串w,w=a*(p，w)=*(p，a)=(q，a)|q
32、*(p，),或,w=a*(p，w)=*(p，a)=*(q,)|q*(p，a),L(NFA)表示被NFA所接收的语言L(NFA)=w|w*且*(Q0，w)F,它表示所有串w的集合 在NFA的状态图中，至少存在一条路径 以w为标记，能使NFA从某个开始状态到达某个接收状态。,构造NFA，分别接收语言,0*、0+(0+1)*、(0+1)+0、01(0+1)*00(0+1)*1(0+1)*00(0+1)*,3.4.2 NFA的确定化,DFA可以转换为NFANFA可以转换为DFA(确定化),定理3-3,*的一个子集L是一个FSL，充要条件为 存在NFA，使得L(NFA)=L,证明：=必要性,若L是FSL
33、，则有L=L(DFA）DFA=(Q，q0，F)构造 NFA=(Q，1，q0，F),1(q，a)=(q，a)即把DFA的一个状态 当作 NFA的一个状态集合 则 L=L(DFA)=L(NFA),证明:=充分性,NFA=（Q，Q0，F）语言L=L(NFA)*构造 DFA=(Q,，q0，F)其中 Q=2Q,q0=Q0Q F Q=p|pQ 且 pF,(p，a)=(q，a)|qp 其中,pQ，a 即(q1，q2，qn，a)=(q1,a),(q2，a),(qn，a),即把NFA的一个状态集合当作是DFA的一个状态。则L=L(NFA)=L(DFA),NFA和DFA是可以互相转换的，是等价的；接收的语言类都是
34、FSL。,例3-18,a,a,b,S2,A,b,S1,a,b,NFADFA,S1和S2是开始状态A是唯一的接收状态该NFA共有3个状态,对于DFA，最多可能有8个状态：，S1，S2，A，S1，A，S2，A，S1，S2，S1，S2，A,DFA状态转换函数,S1，S2,S2,A,S2,A,S2,A,A,A,A,A,A,DFA状态转换图,a,b,a,b,a,b,S1,S2,S2,A,A,注意：,若到达空集状态 实际上就是陷阱状态。,例3-19构造NFA，接收,0，1上的语言，该语言的每个字符串挡成二进制数时，代表的数字能被2整除。,解1:直接构造DFA(以0结尾的串),0,q2,q1,q0,0,1,
35、0,1,1,解2：,正则表达式为：(0+1)*0 直接构造NFA,0,1,q1,0,q0,转换为DFA,0,q1,0,q0,1,1,例3-20 接收,语言L=w|wa,b,c+,|w|1,w中最后字母与第一个字母相同,1)给出该语言的正则表达式；2)构造NFA接受该语言；3)将NFA转换为等价的DFA。,解,1)该语言的正则表达式:a(a+b+c)*a+b(a+b+c)*b+c(a+b+c)*c,解,2)构造NFA接受该语言,解,3)改造为DFA接受该语言：a b c q0 q1 q2 q3 q1 q1,q4 q1 q1 q2 q2 q2,q4 q2 q3 q3 q3 q3,q4 q1,q4
36、q1,q4 q1 q1 q2,q4 q2 q2,q4 q2 q3,q4 q3 q3 q3,q4,思考：构造NFA，接收,语言L=w|wa,b,c+,|w|0,w中最后字母与第一个字母相同该语言的正则表达式:a(R)*a+b(R)*b+c(R)*c+a+b+c,例3-21接收,语言L=w|wa,b+,w中倒数第二个字母肯定在前面出现过,1)给出该语言的正则表达式；2)构造NFA接受该语言；3)将NFA转换为等价的DFA。,解,1)该语言的正则表达式:(a+b)*a(a+b)*a(a+b)+(a+b)*b(a+b)*b(a+b),解,2)构造NFA接受该语言,解,3)将NFA转换为等价的DFA,例
37、:构造NFA，接收,0，1上的语言;该语言的每个句子必须包含00,正则表达式为：(0+1)*00(0+1)*,NFA,0,1,q2,0,q0,0,1,q1,0,构造NFA，接收,0，1上的语言，该语言的每个句子必须包含001,正则表达式为：(0+1)*001(0+1)*,NFA,0,1,q2,001,q0,0,1,例3-23构造NFA，接收,0，1上的语言，该语言每个句子必须不包含001,NFA,0,q1,0,1,1,q2,0,q0,例3-24构造NFA，接收,0，1上的语言，该语言的每个句子 以0开头，以1结尾。,NFA,q2,0,q0,0,1,q1,1,例3-25构造NFA，接收,0，1上
38、的语言，该语言的句子 若以1结尾,则该字符串长度为偶数 若以0结尾,则该字符串长度为奇数,NFA(无),q4,0,1,0,1,0,q3,q2,q1,1,思考,若还需要接收，如何构造NFA？,一般：,NFA适于构造（已知正则表达式）的语言：满足条件 的语言 包含子串 以串开始或结束(倒数)第个字母是,定理3-4,每个右线性语言(正则语言)是一个FSL。,证明,L是右线性语言，则L=L(G)G=（，V，S，P）首先消除G中一般的产生式,构造NFA将文法非终结符当作NFA的状态增加一个接收状态q,NFA=(Q，Q0，F)其中：Q=V U q Q0=S F=q,注意,若文法G中有S,即L 则开始状态S
39、也是接收状态,(A，x)=B|AxB在P中 q|Ax在P中所以，L=L(G)=L(NFA),而NFA又和DFA是等价的，一个右线性语言也是一个FSL。,总之,右线性语言和FSL是等价的，右线性文法产生右线性语言；有限状态自动机接收FSL；也都是正则集。,例3-26 构造NFA，接收,0，1上的语言 L=0n1m2k|n,m,k0,NFA状态转移图,q0,0,1,0,1,2,2,q1,q2,q3,或,q0,0,1,0,1,2,2,q1,q2,q3,例3-27构造NFA，接收,0，1上的语言 L=0n1m2k|n,m,k=0,0,1,0,1,2,2,q3,q0,q1,q2,2,1,2,或 多个开始
40、状态的NFA,1,0,2,2,q3,q1,q2,1,2,3.5 带动作的有限状态自动机,对于FA（DFA、NFA），有(q，)=q*(q，)=q(q，)=q*(P，)=P,表示FA不读入任何字母(即只扫描空串时)，FA的状态不发生改变，并且读头不进行移动，仍然指向当前非空字符。,若允许FA在不读入任何字符时,FA的状态可以发生改变，则FA为带有动作的FA,定义3-14带动作的有限状态自动机,带有动作的FA是一个五元式,-FA=(Q，Q0，F)Q，Q0，F的含义同NFA,:Q 2Q(q，a)2Q(q，)2Q,即,具体,(q,)=q 表示自动机在状态q时，不读入任何字母，自动机状态不变 并且读头不
41、移动；,(q，a)=表示自动机在读入字母a后，自动机停机。,(q，a)=p1，p2，p3，pm 表示自动机在读入字母a后，自动机的状态可以选择地改变为p1，p2，p3，或者pm 并将读头向右移动一个单元；,(q,)=q1，q2，q3，qn 表示自动机在状态q时，不读入任何字母，自动机的状态可以选择地改变为q1，q2，q3，或qn 并且读头不移动；,注意,带有动作的FA一定是NFA。一般，记为-NFA。,例3-28,使用-NFA接收语言 L=0*1*2*即 L=0n1m2k|n,m,k=0,状态图,0*1*2*,q0,q1,q2,2,0,1,对应的5个函数为：(q0，0)=q0(q0，)=q1(
42、q1，1)=q1(q1，)=q2(q2，2)=q2,定义3-15,对于-NFA，qQ 从q开始，扫描1个或多个后能够到达的状态集记为-CLOSURE(q),-CLOSURE(q)=p|扫描后能够从q到达p,对于-NFA，qQ-CLOSURE(q)是由递归规则确定的状态集：,规则,(1)q-CLOSURE(q)即任意状态q接收空串，至少都能保持状态q不变；,规则,(2)如果p-CLOSURE(q)则(p,)-CLOSURE(q)(3)重复(2)，直到-CLOSURE(q)中的状态不再增加为止。,注意,-CLOSURE(q)与(q,)不同,进一步,对于状态集合P，定义-CLOSURE(P)=,qP
43、,-CLOSURE（q）,定义3-16 扩展的状态转换函数,-NFA 扩展状态转换函数*：2Q*2Q为*（P，w）=Q 即自动机在状态集合P时，扫描串w后到达的状态集合Q,空串,*(q,)=-CLOSURE(q)*(P,)=-CLOSURE(P),单个字母,*(q，a)=*(q，a)=-CLOSURE(p,a)*(P，a)=*(q，a),qP,p*(q,),对于串wa,*(P,wa)=*(*(P,w),a),或,*(P,aw)=*(*(P,a),w),对于,-CLOSURE(q0)=-CLOSURE(q1)=-CLOSURE(q2)=,q0,q1，q2,q2,q1,q2,对于,*(q0,)=-
44、CLOSURE(q0)=q0，q1，q2,*(q0,0)=*(q0,0)=-CLOSURE(p,0)p*(q0,)=-CLOSURE(q0,0)(q1,0)(q2,0)=-CLOSURE(q0)=q0，q1，q2,*（q0,01）=*(*(q0,0),1)=*(q0,q1,q2,1)=-CLOSURE(q0,1)(q1,1)(q2,1)=q1,q2,注意,*(q，)与(q，)不同,定理3-5,如果语言L被-NFA接收，则 该语言L也能够被一个NFA接收,证明：,假设语言L被一个-NFA接收,-NFA=(Q，Q0，F),1)构造 NFA1=(Q，1，Q0，F1)其中:对于a 1(q，a)=*（q
45、，a）,F1=Fq0 若 F-CLOSURE(q0)F1=F 若 F-CLOSURE(q0)=,2）证明对于w+,有 1(q0，w)=*（q0,w）,结论,如果语言L被-NFA接收，则语言L也能够被一个NFA接收,例3-29,将-NFA改造为等价的NFA。,q0,q1,q2,2,0,1,q1,q0,q2,2,0,1,0,1,1,2,0,1,2,例3-30构造-NFA,接收,0，1上的语言 L=0k|k=0，k能够被2或3整除即L=02n或03m|n,m=0,q0,q1,q3,q2,q4,q5,0,0,0,0,0,思考,L=02n+3m|n,m0,请验证,q0,q5,q1,0,q2,0,q3,0
46、,q4,0,0,0,0,思考：,-NFA转换为NFA能否 先将-NFA转换为“右线性”文法，再转换为NFA？引进单产生式AB,3.6 有限状态自动机的一些变形,有限状态自动机存在变形。,双向的有限状态自动机,在处理输入串的过程中，双向的有限状态自动机的读头 可以向右移动一个单元；也可以向左移动一个单元；也可以不移动。,定义3-18,确定的双向的有限状态自动机(2DFA)是一个五元式：2DFA=（Q，q0，F）其中，Q,q0，F的含义同DFA,：状态转换函数；QQL，R，N 对于qQ，a,(q，a)=p，D,2DFA在状态q读入字母a 自动机状态将变为p状态 D=L 读头向左移动一个单元 D=R
47、 读头向左移动一个单元 D=N 读头位置不变；,2DFA格局描述同DFA,2DFA=（Q，q0，F）接收的语言为L(2DFA)L(2DFA)=w|q0w=*q，qF,定理3-6,2DFA与DFA等价。证明：略。,可以定义不确定的双向的有限状态自动机。,定义3-20,不确定双向有限状态自动机2NFA是一个五元式：2NFA=(Q，Q0，F)其中 Q，Q0，F的含义同NFA,：状态转换函数；：Q2QL，R，N,对于qQ，a,D1，D2，DmL,R,N，,(q,a)=(p1,D1),(p2,D2),(pm,Dm)2NFA在状态q读入字母a 可以将状态变为pi 按照Di实现对读头的移动,定理3-7,2N
48、FA与NFA等价。证明：略。,带输出的有限状态自动机,FA，对于某个输入串w 得到的结论是:是否接收该串；或FA输出“是”或“否”。,存在许多有穷状态系统对于不同的输入信号，除系统内部的状态变化之外，还向系统外部输出各种信号。,模型图,有限状态系统,输入序列,输入序列,典型带输出的有穷自动机-Moore机和Mealy机。由于它们带有输出，从抽象的角度考虑，就没有必要再设置接收状态（集）。,定义3-21,Moore机是一个六元式：Moore M=(Q,q0)其中 Q，q0，的含义同FA：输出字母表,输出函数：Q 对于qQ，a(q)=a表示Moore机处于状态q时输出a,Moore机,在读入输入串
49、的过程中状态不断发生改变并且在每个状态上都有输出,对于输入串a1a2a3an-1an,设(q0,a1)=q1(q1,a2)=q2(qn-2,an-1)=qn-1(qn-1,an)=qn,则,Moore机的输出序列可以表示为：(q0)(q1)(q2)(qn),如果输入串的长度为n,则Moore机的输出串的长度为n+1。,实际上,FA只是Moore机的一个特例。,若Moore机的输出仅只有F或T 将输出T的状态当作接收状态，Moore机就是一般的FA。,例3-31设计Moore机,=0，1 若将输入串当作二进制数，则在读入串的过程中，希望输出已经读过的（数字）串模3的余数。,分析,模3的余数只能是
50、0、1和2 输出字母表=0，1，2 状态q0、q1和q2对应3种余数,状态上的标记表示Moore机在该状态时的输出,q0,q1,q2,0,1,2,0,0,0,1,1,1,当输入为1010时 状态变换的序列为 q0 q1 q2 q2 q1输出 0 1 2 2 1,即,当输入时，输出余数0当输入1时，输出余数1当输入10时，输出余数2当输入101时，输出余数2当输入1010时，输出余数1,定义3-22,Mealy机是一个六元式：Mealy M=(Q,，,q0)其中Q，q0，的含义同FA：输出字母表,输出函数：Q对于qQ，x，a(q，x)=a表示Moore机在状态q,读入字母x时，输出a,Mealy
