《形式语言与自动机》课件ch3.9-3.10.ppt

1、12023-5-22School of Computer Science,BUPT3.9 右线性语言的性质右线性语言的性质主要内容：主要内容：DFA的极小化泵浦引理右线性语言的封闭性22023-5-22School of Computer Science,BUPT确定有限自动机确定有限自动机DFA的化简的化简(极小化极小化)对DFA M的极小化是找出一个状态数比M少的DFA M1，使满足 L(M)=L(M1)1等价和可区分的概念 设DFA M=(Q，T，q0，F)对不同的状态q，qQ 和每个T*，如果有(q，)*(q，)必有(q，)*(q，)且qF，则称q与q状态等价.记为qq 否则，称q，q

2、可区分。32023-5-22School of Computer Science,BUPT确定有限自动机确定有限自动机DFA的化简的化简2不可达状态 如果不存在任何T*，使(q，)*(q，)，则称状态qQ为不可达状态。3 最小化 若DFA 不存在互为等价状态及不可达状态，则称DFA 是最小化的。42023-5-22School of Computer Science,BUPT最小化算法最小化算法 一个DFA 的最小化，是把的状态集构成一个划分。即:任何两个子集的状态都是可区分的；同一子集中的任何两个状态都是等价的。之后，每个子集用一个状态代表，并取一个状态名。构成划分的步骤构成划分的步骤:1.

3、构成基本划分 =，”，(为终态集，”为非终态集)2.细分=1，2，n，i i =q，q，q当输入任意字符a时，若i中的状态经标a的边可到达的状态集的元素分属于两个不同的子集中，则将i 细分为两个子集.重复步骤(2)，直至不可再细分，得到1.若1中有不可达状态，将其删除，1便是最小化的.52023-5-22School of Computer Science,BUPT例例(1)q，q为不可达状态，删除之.(2)Q=q，q，q，q，q,=q，q，q，q，q 构成基本划分 =，”(a)对于=q，q，对字符a，有(q，a)=q，(q，a)=q q，q 同一子集.对字符b，有(q，b)=q，(q，a)=

4、q q，q 同一子集.=q，q 不能再细分.(b)对于”=q，q，q对a，(q,a)=q，(q,a)=q，(q,a)=q q,q同一子集对b，(q,b)=q，(q,b)=q，(q,b)=q q，q，q 同一子集 将再分解.=q，q1，q3，(c)重复步骤(2)，q，q 不能再细分，可用q表示.q1，q3 不可再细分，用q1表示 q，q，q 62023-5-22School of Computer Science,BUPT计算状态集划分的算法计算状态集划分的算法 填表法填表法 填表算法（填表算法（table-filling algorithm）基于如下递归地基于如下递归地 标记可区别的状态偶对的

5、过程标记可区别的状态偶对的过程:-基础基础 如果如果 p 为终态，而为终态，而 q 为非终态，则为非终态，则 p 和和 q 标记标记 为可区别的；为可区别的；-归纳归纳 设设 p 和和 q 已标记为可区别的已标记为可区别的,如果状态如果状态 r 和和 s 通过某个通过某个 输入符号输入符号 a 可分别转移到可分别转移到 p 和和 q，即即 (r,a)=p,(s,a)=q,则则 r 和和 s 也标记为可区别的；也标记为可区别的；这是因为：这是因为：若若 p 和和 q 可为字符串可为字符串 w 区别区别,则则 r 和和 s 可可 为字符串为字符串 aw 区别区别.（(r,aw)=(p,w),(s,

6、aw)=(q,w)）72023-5-22School of Computer Science,BUPT计算状态集划分的算法计算状态集划分的算法 填表法填表法 填表算法举例填表算法举例212334455667xxxxxxxxxxxxx651Start3724aaaaaaabbbbbbb(1)区别所有终态和非终态区别所有终态和非终态(2)区别区别(1,3),(1,4),(2,3),(2,4),(5,6),(5,7)xxxxx(3)区别区别(3,4)x(4)结束结束.划分结果：划分结果：1,2,3,4,5,6,782023-5-22School of Computer Science,BUPT通过合

7、并等价的状态进行通过合并等价的状态进行 DFA 的优化的优化 步骤步骤 1.删除所有从开始状态不可到达的状态及与其相关的边删除所有从开始状态不可到达的状态及与其相关的边,设所得到的设所得到的 DFA 为为 A=(Q,T,q0,F)；2.使用填表算法找出所有等价的状态偶对；使用填表算法找出所有等价的状态偶对；3.根据根据 2 的结果计算当前状态集合的划分块，每一划分的结果计算当前状态集合的划分块，每一划分 块中的状态相互之间等价，而不同划分块中的状态之块中的状态相互之间等价，而不同划分块中的状态之 间都是可区别的间都是可区别的.包含状态包含状态 q 的划分块用的划分块用 q 表示表示.4.构造与

8、构造与 A 等价的等价的 DFA B=(QB,T,B,q0,FB),其中其中 QB=q|q Q,FB=q|q F,B(q,a)=(q,a)92023-5-22School of Computer Science,BUPT通过合并等价的状态进行通过合并等价的状态进行 DFA 的优化的优化 举例举例 651Start3724aaaaaaabbbbbbb 划分结果：划分结果：1,2,3,4,5,6,7 等价的状态偶对为：等价的状态偶对为：（1,2）,（6,7）新的状态集合：新的状态集合：1,3,4,5,6651Start34aaaabbbbba102023-5-22School of Compute

9、r Science,BUPT最小化的最小化的 DFA 课堂练习课堂练习 最小化下列最小化下列 DFA:651Start3724aaaaaaabbbbbbb 参考结果参考结果61Start34aaaabbbb112023-5-22School of Computer Science,BUPT针对正则语言的针对正则语言的 Pumping 引理引理 正则语言应满足的一个必要条件 用于判定给定的语言不是正则集。物理意义：物理意义：当给定一个正则集和该集合上一个足够长的字符串时，在该字符串中能找到一个非空的子串，并使子串重复，从而组成新的字符串。该新串必在同一个正则集内。定理：定理：设L是正则集，存在常

10、数k，对字符串 且，则可写成10，其中10，0，对所有的0有10i2。证明证明 设设 L 是是 DFA D=(Q,T,q0,F)的语言，的语言，取取 k=|Q|即可即可.122023-5-22School of Computer Science,BUPTDFA 的的“Pumping”特性特性 设 DFA D=(Q,T,q0,F),|Q|=n.对于任一长度不小于 n 的字符串 w=a1a2am,其中 mn,akT(1 k m),qQ,考察如下状态序列 p0=q p1=(q,a1)p2=(q,a1a2)pn=(q,a1a2an)pn+1=(q,a1a2an+1)pm=(q,a1a2am)由pige

11、onhole 原理,p0,p1,p2,pn 中至少有两个状态是重复的，即存在 i,j,0ijn,pi=pj.“pumping”特性：任一长度不小于状态数目 的字符串所标记的路径上，必然出现重复的状态.132023-5-22School of Computer Science,BUPTDFA 的的“Pumping”特性特性“pumping”特性：特性：如前如前,设设 DFA D=(Q,T,q0,F),|Q|=n,w=a1a2am(m n),则存在则存在 i,j,0 i j n,pi=pj,其中其中pk=(p0,a1a2ak),0 k m.若假定若假定p0=q0,pm F,即即w L(D).令令

12、w=xyz,其中：其中：x=a1a2ai,y=ai+1ai+2aj,z=aj+1aj+2am 则对任何则对任何k 0，都有都有 xykz L(D).(参考下图参考下图)Startp0pipmx=a1a2aiy=ai+1ai+2ajz=aj+1aj+2am142023-5-22School of Computer Science,BUPTPumping 引理的应用引理的应用（用于证明某个语言用于证明某个语言 L 不是正规语言）不是正规语言）证明步骤证明步骤 1.选任意的选任意的n.2.找到一个满足以下条件的串找到一个满足以下条件的串w L(长度至少为长度至少为n).3.任选满足任选满足w=xyz

13、 y|xy|n 的的x,y,z 4.找到一个找到一个 k 0,使使 xykz L.举例举例 证明证明L=anbn|n1 不是正则集不是正则集.证明证明:由泵浦引理，假设由泵浦引理，假设L是正则集，则对足够大的是正则集，则对足够大的n，anbn可写成可写成102，其中其中0 n 0中不可能含中不可能含 b+，否则不满足，否则不满足0|10|n.0只可能取只可能取 a+，设设|0|=k1，k为常数，为常数，取取i=0，有有1002=12=an-kbn，此时，此时，a，b字符个数不字符个数不同同,即新组成的串即新组成的串12 L.与假设矛盾，故与假设矛盾，故L不是正则集不是正则集.152023-5-

14、22School of Computer Science,BUPTPumping 引理的应用引理的应用 例例 证明证明kk的整数不是正则集的整数不是正则集.证明证明 假设假设L是正则集，取足够大的整数是正则集，取足够大的整数n，.有有102=n 2 n，00n，010n 取取i=2，有有n21022 n2+n (n+1)2 10i2 (串长不是整数的平方串长不是整数的平方)与假设矛盾。与假设矛盾。L不是正则集。不是正则集。162023-5-22School of Computer Science,BUPT右线性语言的封闭性右线性语言的封闭性 上节从文法产生的角度证明了右线性语言及其并，积，闭上

15、节从文法产生的角度证明了右线性语言及其并，积，闭包是正则集；本节用有限自动机接受的语言来证明。包是正则集；本节用有限自动机接受的语言来证明。(书书P72)1.1.设设和和是右线性语言，证明是右线性语言，证明为右线性语言为右线性语言 构造NFA M(Q，T，q0，F)QQ1Qq0 q0是新的起始状态当，q 否则 F=M形如形如:172023-5-22School of Computer Science,BUPT右线性语言的封闭性右线性语言的封闭性 2.设设和和是右线性语言，证明是右线性语言，证明为右线性语言为右线性语言(书书P73)构造NFA M(Q，T，q0，F),其中Q=QQ q0=q1 当

16、q2F2 当q2F2 F=M形如形如:182023-5-22School of Computer Science,BUPT右线性语言的封闭性右线性语言的封闭性 3.设设是右线性语言，证明是右线性语言，证明L*是右线性语言是右线性语言(书书P106)构造构造NFA M(Q，T，q0，F),Q=Q1q q是新的起始状态是新的起始状态,F=1qL*形如形如 192023-5-22School of Computer Science,BUPT右线性语言的封闭性右线性语言的封闭性 4.设设是右线性语言，证明是右线性语言，证明 L 是右线性语言是右线性语言证明：证明：构造接受构造接受1的的M(Q，T，q0

17、，F)其中其中Q=Q1 是一个新状态是一个新状态 T T1 q0=q1 (Q11)(即将即将1的终止状态变为的终止状态变为M的非终止状态的非终止状态)定义为定义为:当当aT1，则则(q，a)=1(q，a)保留原有函数保留原有函数 当当aT1 且且1(q，a)=，则则(q，a)=当当aTT1，则则(q，a)=遇到原来没有的字符全转至遇到原来没有的字符全转至.对任意对任意aT，(，a)202023-5-22School of Computer Science,BUPT右线性语言的封闭性右线性语言的封闭性 例例:(:(书书P76)P76)对下图的对下图的1,求求(1 1)212023-5-22Sch

18、ool of Computer Science,BUPT右线性语言的封闭性右线性语言的封闭性 例例:设设DFA1（q,q,，q,q,q）对，对，,求求(1)222023-5-22School of Computer Science,BUPT右线性语言的封闭性右线性语言的封闭性 5.证明证明1是封闭的是封闭的 证明：证明：11 得证得证6.证明右线性语言对于置换是封闭的证明右线性语言对于置换是封闭的.(略略-自学自学)232023-5-22School of Computer Science,BUPT有关正则语言的几个判定性质 判定正判定正则则语言是否为空语言是否为空 判定正判定正则则语言中是否

19、包含特定的字符串语言中是否包含特定的字符串 判定两个正判定两个正则则语言是否相等语言是否相等242023-5-22School of Computer Science,BUPT 判定正判定正则则语言是否为空语言是否为空 可由如下步骤递归地计算可达状态集合：可由如下步骤递归地计算可达状态集合：-判定算法判定算法 测试从测试从 初态是否可达某一终态初态是否可达某一终态.先求所有可先求所有可 达状态的集合，若其中包含终态，则该正规语言非空，达状态的集合，若其中包含终态，则该正规语言非空，否则为空语言。否则为空语言。-算法复杂度算法复杂度 设有限自动机的状态数目为设有限自动机的状态数目为 n，上述判定

20、上述判定 算法的复杂度为算法的复杂度为 O(n2).基础基础：初态是可达的：初态是可达的：归纳归纳：设状态：设状态 q 是可达的，若对于某个输入符号或是可达的，若对于某个输入符号或 ，q 可转移到可转移到 p，则则 p 也是可达的：也是可达的：252023-5-22School of Computer Science,BUPT 判定正判定正则则语言中是否包含特定的字符串语言中是否包含特定的字符串-判定算法判定算法 从初态开始，处理输入字符串从初态开始，处理输入字符串 w，如果可如果可 以结束于某一终态，则该正规语言中包含以结束于某一终态，则该正规语言中包含 w，否则不否则不 包含包含 w。-算

21、法复杂度算法复杂度 设输入字符串设输入字符串w 的长度的长度|w|=n，上述判定上述判定 算法的复杂度为算法的复杂度为 O(n).以以 DFA 表示正规语言表示正规语言 以正规表达式表示正规语言以正规表达式表示正规语言将其转化为等价将其转化为等价的的-NFA，然后执行上述过程然后执行上述过程.以以 NFA（或或-NFA）表示正规语言表示正规语言 可以将其转化为可以将其转化为等价的等价的 DFA，然后执行上述过程；也可以直接模拟其处然后执行上述过程；也可以直接模拟其处理字符串的过程，判定算法的复杂度为理字符串的过程，判定算法的复杂度为 O(n2s),其中其中n为为字符串的长度，字符串的长度，s为

22、为NFA（或或-NFA）的状态数目的状态数目.262023-5-22School of Computer Science,BUPT 判定两个正判定两个正则则语言是否相等语言是否相等 判定算法判定算法 可由采取如下步骤：可由采取如下步骤：算法复杂度算法复杂度 以上算法的复杂度即填表算法的以上算法的复杂度即填表算法的 复杂度，其上限为复杂度，其上限为O(n4)；可以适当设计填表可以适当设计填表 算法的数据结构，使其复杂度降为算法的数据结构，使其复杂度降为 O(n2).1.先将两个正规语言的表达形式都转化为先将两个正规语言的表达形式都转化为 DFA，问题问题 转化为两个转化为两个DFA是否是等价的；

23、是否是等价的；2.适当重命名，使两个适当重命名，使两个DFA没有重名的状态；没有重名的状态；3.将两个将两个DFA相并，相并，构造一个新的构造一个新的DFA，原来的终态原来的终态仍是终态，转移边不发生任何变化，取任何一个状态仍是终态，转移边不发生任何变化，取任何一个状态为初态；为初态；4.对新构造的对新构造的DFA运用填表算法，如果原来运用填表算法，如果原来DFA的两个的两个初态不可区别，则这两个正规语言相等，否则不相等初态不可区别，则这两个正规语言相等，否则不相等.272023-5-22School of Computer Science,BUPT 3.10 双向和有输出的有限自动机双向和有

24、输出的有限自动机 主要内容：主要内容：双向有限自动机有输出的有限自动机米兰机摩尔机282023-5-22School of Computer Science,BUPT双向有限自动机双向有限自动机(2DFA)定义定义:n读入一个字符之后，读头既可以左移一格，也可以右移一格，或者不移动的有限自动机，为双向有限自动机.n确定的双向有限自动机:每读入一字符，必须向左或右移动，不考虑不移动的情况.292023-5-22School of Computer Science,BUPT2DFA的形式定义2DFA M(Q，T，q0，F)是从是从QTQL，R的映射的映射.即即(q，a)=(p，R)或或 (q，a)

25、=(p，L)（在状态在状态q，读入读入a，进入状态进入状态p，读头向右读头向右(向左向左)移一格）移一格）用格局描述用格局描述:设有设有1q2 1 -已输入串已输入串q -当前状态当前状态 2 -待输入串待输入串(q，am+1)=(p，R)的格局表示的格局表示:a1 a2am q am+1an a1 a2am+1 p am+2an(q，am+1)=(p，L)的格局表示的格局表示:a1 a2am q am+1an a1 a2am-1 p am am+1an 302023-5-22School of Computer Science,BUPT2DFA2DFA接受的字符串集合是接受的字符串集合是:L

26、(M)=|q*q，q F例例:书书P78 例例1.其状态图为其状态图为b,R312023-5-22School of Computer Science,BUPT有输出的有限自动机有输出的有限自动机 有输出的有限自动机是有限自动机的一个类型有输出的有限自动机是有限自动机的一个类型.这类自动机在有字符输入时，不仅存在状态转换，这类自动机在有字符输入时，不仅存在状态转换，同时引起字符输出同时引起字符输出.根据输入字符，自动机状态，输出字符三者之根据输入字符，自动机状态，输出字符三者之间关系，可有两类有输出的自动机间关系，可有两类有输出的自动机:n 米兰机米兰机(Mealy):输出字符与输入字符及状态

27、有关输出字符与输入字符及状态有关.n 摩尔机摩尔机(Moore):输出字符仅与状态有关输出字符仅与状态有关.最大优点最大优点:节省状态节省状态!322023-5-22School of Computer Science,BUPT米兰机米兰机米兰机米兰机形式定义形式定义:M(Q，T，R，g，q0)其中其中 Q 有限状态集合有限状态集合 T 有限输入字母表有限输入字母表 R 有限输出字母表有限输出字母表 :QTQ 转换函数转换函数 g:QTR 输出函数输出函数 q0:初始状态初始状态 q0 Q和和g函数共同描述了米兰机的工作状况函数共同描述了米兰机的工作状况.332023-5-22School o

28、f Computer Science,BUPT米兰机米兰机米兰机米兰机图形表示图形表示:(p(p，a)=qa)=q g(pg(p，a)=ba)=b Pqa/b例例:(P79 例2)设计米兰机，其输出是输入字符个数的模3数解解:输出字母表R=0，1，2.设输入字母表T=a,M的状态数应有3个，记录已输入字符个数的模3数.Q=q0，q1，q2 分别表示输入字符数模3=0,1,2342023-5-22School of Computer Science,BUPT米兰机米兰机例例:（P80 例3）设计米兰机，其输入0，1*，当输入串有奇数个1时，输出1.当输入串有偶数个1时，输出0.解解:需二个状态q

29、0，q1 q0 表示输入串有偶数个1，q1 表示输入串有奇数个1352023-5-22School of Computer Science,BUPT习题习题1 设语言L由0，1组成，且字符串的最后两个字符相同.构造米兰机M，输出Y/N表示输入串是否属于L.解解:设状态集Q为 初始状态q0 状态p0 表示输入串最后字符为0 状态p1 表示输入串最后字符为1362023-5-22School of Computer Science,BUPT习题习题2练习练习:(书书P93 19题题)设计米兰机，输入是0，1组成的串，要求输出串对输入串延迟两个时间单位.解:M(Q，T，R，g，q0)，T=0，1 R

30、=0，1 分析分析:可能的状态-即一个输入在输出前可能处于的状态 Q:00 q00 01 q01 10 q10 11 q11 Q=q00，q01，q10，q11372023-5-22School of Computer Science,BUPT习题习题2初始情况初始情况:刚开始工作时输入前两个字符，输出为 382023-5-22School of Computer Science,BUPT摩尔机摩尔机 摩尔机的输出只与到达的状态有关摩尔机的输出只与到达的状态有关 形式定义形式定义:M(Q，T，R，g，q0)g:Q R:Q T Q 图形表示图形表示:(q(q，a)=pa)=p g(p)=bg(p

31、)=b2 2 q,b1p,b2a392023-5-22School of Computer Science,BUPT摩尔机摩尔机例例:(书P81 例4)设计自动机，其输入串0，1*，输出是(n1-n0)mod 4，n0是中含0的个数，n1是中含1的个数。四个状态 q0，q1，q2，q3 分别输出0，1，2，3 解解:需四个状态，取输出字母表 R=0，1，2，3.402023-5-22School of Computer Science,BUPT习题习题3 设计摩尔机，接受0，1组成的串，串的首符为1，串中出现且只出现一个0。若接受输出Y，否则输出N。解解:L的串应为11*01*M(Q，T，R，

32、g，q0)T=0，1，R=Y，N 设计状态 初始状态 拒绝接受 可能接受 接受Q:412023-5-22School of Computer Science,BUPT米兰机和摩尔机的变换米兰机和摩尔机的变换 n 已知摩尔机可构造等价的米兰机已知摩尔机可构造等价的米兰机设 摩尔机(Q,T,R,g,q0)米兰机(Q,T,R,g,q0)如果中有(q，a)=p，g(p)=b则中有g(q，a)=b=g(q，a)例例:摩尔机摩尔机米兰机米兰机 422023-5-22School of Computer Science,BUPT米兰机和摩尔机的变换米兰机和摩尔机的变换 n 由米兰机也可构造等价的摩尔机（略）由米兰机也可构造等价的摩尔机（略）n 小结小结 双向自动机，米兰机，摩尔机的共同优点是描述问题清晰，且节省状态.例如例如:对L=(0+1)*(00+11)(前面米兰机的例子)米兰机只需三个状态 而用DFA则不会少于5个状态