形式语言与自动机精品文稿.ppt

《形式语言与自动机精品文稿.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机精品文稿.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、形式语言与自动机第1页，本讲稿共38页22022/10/21College of Computer Science&Technology,BUPT-NFA 的形式定义 一个 -NFA 是一个五元组 A=(Q,T,q0,F).n 有限状态集有限状态集n n 有限输入符号集有限输入符号集n n 转移函数转移函数n n 一个开始状态一个开始状态n n 一个终态集合一个终态集合q0 Qn F Qn 与与 NFA 的不同之处的不同之处 :Q (T )2Q第2页，本讲稿共38页32022/10/21College of Computer Science&Technology,BUPT-NFA 如何接受输入

2、符号串q1q0q2q3q5 ,+,q4n 该该 -NFA 可以接受的字符串如：可以接受的字符串如：n n 3.14n+.314n 314.第3页，本讲稿共38页42022/10/21College of Computer Science&Technology,BUPT二、-闭包（closure）概念n 状态 q 的-闭包，记为 -CLOSURE 或ECLOSE，定义为从 q 经所有的 路径可以到达的状态（包括q自身），如：q0q1q2012n -CLOSURE(q0)=q0,q1,q2 n -CLOSURE(q1)=q1,q2 n -CLOSURE(q2)=q2 第4页，本讲稿共38页5202

3、2/10/21College of Computer Science&Technology,BUPT状态子集状态子集I I 的的-闭包：闭包：-CLOSURE(I)-CLOSURE(q)qI例：例：-CLOSURE(q1，q2)-CLOSURE(q1)-CLOSURE(q2)q1，q2nIa Ia 概念：概念：对于状态子集对于状态子集I Q，任意，任意aT，定义，定义Ia如下：如下：Ia=-Closure(P)其中其中P=（I，a）.即即P是从是从I中的状态经过一条标中的状态经过一条标a的边可以到达的状态集合的边可以到达的状态集合第5页，本讲稿共38页62022/10/21College of

4、 Computer Science&Technology,BUPT例：例：I Iq0q0，q1q1，求，求I I1 1I I1 1 -CLOSURE-CLOSURE（I I，1 1）-CLOSURE-CLOSURE（q0q0，q1q1，1 1）-CLOSURE-CLOSURE（q1 q1）q1q1，q2q2q0q1q2012第6页，本讲稿共38页72022/10/21College of Computer Science&Technology,BUPT扩展转移函数适合于输入字符串n 设一个设一个 -NFA,:Q T 2Q n n 扩充定义扩充定义 :Q T*2Q n 对任何对任何q Q，定义：

5、，定义：n 1 (q,)=ECLOSE(q)n 2(q，a)-CLOSURE(P)其中其中P p|存在存在r(q，)p(r，a)注意：注意：此时此时(q，a)(q，a)，因为因为(q，a)表示由表示由q出发，只沿着标出发，只沿着标a 的路径所能到达的状态，的路径所能到达的状态，而而(q，a)表示由表示由q出发，沿着标出发，沿着标a(包括包括转换在内转换在内)的路径所能到达的状态的路径所能到达的状态.第7页，本讲稿共38页82022/10/21College of Computer Science&Technology,BUPT-NFA中，中，与与函数的不同函数的不同 n 举例举例 计算计算 (

6、q0,a)(q0，)-CLOSURE(q0)q0，q2(q0，a)-CLOSURE(q0，)，a)-CLOSURE(q0，q2，a)-CLOSURE(q0，a)(q2，a)-CLOSURE(q1 q3)q1，q2 q3q1，q2，q3同理：同理：(q0，aa)q3-CLOSURE(q0)q0，q2-CLOSURE(q1)q1，q2-CLOSURE(q2)q2-CLOSURE(q3)q3第8页，本讲稿共38页92022/10/21College of Computer Science&Technology,BUPT三、-NFA 的 语 言n 设一个设一个 -NFA M=(Q,T,q0,F)n n

7、 定义定义M 的语言：的语言：n L(M)=|(q0,)F n 即即 满足满足(q0，)含有含有F的一个状态的一个状态n 第9页，本讲稿共38页102022/10/21College of Computer Science&Technology,BUPT四、有四、有 转换的转换的NFA与无与无 转换的转换的NFA的等价的等价1.-NFANFA具有转移的NFA是不具转移的NFA的一般情况,所以只要证明下面的定理即可:定定理理:如如果果L被被一一个个具具有有 转转移移的的NFA接接收收,那那么么L可可被一个不具被一个不具 转移的转移的NFA接收接收.证证明明思思路路:构构造造一一个个不不具具 转转

8、移移的的NFA,证证明明其其接接收收具有具有 转移的转移的NFA所接受的语言所接受的语言.第10页，本讲稿共38页112022/10/21College of Computer Science&Technology,BUPT从 -NFA 构造等价的 无 NFAn设设M=(Q,T,q0,F)是是一一个个-NFA,可可构构造造一一个个无无 的的NFAM1=(Q,T,1,q0,F1),对任何对任何a T,1(q,a)=(q,a).(注意注意与与的区别与联系。而的区别与联系。而1和和1是相等的。是相等的。F1 F q0若若-CLOSURE(q0)F F否则否则第11页，本讲稿共38页122022/10

9、/21College of Computer Science&Technology,BUPT从 -NFA 构造等价的 无 NFA证明证明:采用归纳法证明采用归纳法证明1（q0，）（q0，），），|=1|=1。当当|w|=0,即即 w=时，不一定相等时，不一定相等.1(q0，)q0，而而(q0，)-CLOSURE(q0)因此，从因此，从|1开始证明开始证明 1.当当|=1时，定义相等。时，定义相等。由由1定义定义 1（q0，a）（q0，a）第12页，本讲稿共38页132022/10/21College of Computer Science&Technology,BUPT设当设当|=n时，时，1

10、（q0,）=（q0,），），则则当当|a|=n+1时，时，左侧左侧 1（q0,a）1(1（q0，），a)1(（q0，），），a)由归纳假设由归纳假设1(R，a)设设R（q0，）1(q，a)q R(q，a)q R.由由1定义定义(R，a)(（q0，），），a)R（q0，）(q0，a)右侧右侧再再证证:1（q0，）含含F1的的一一个个状状态态当当且且仅仅当当（q0，）含含F的的一一个个状态状态 （略）（略）第13页，本讲稿共38页142022/10/21College of Computer Science&Technology,BUPT证明同时展示了一种将证明同时展示了一种将-NFA转化为转化为

11、NFA的方法的方法.-NFANFADFA例：将将-NFA转换为转换为NFA.（图3.4.1，3.4.3）q0q1q2012q0q1q20120,11,20,1,2第14页，本讲稿共38页152022/10/21College of Computer Science&Technology,BUPT举例q1q0q2q3q5 ,+,q4q0 q1q1 q4q2q2 q3 q5q3 q5第15页，本讲稿共38页162022/10/21College of Computer Science&Technology,BUPT第五节正则集和正则式n正则集：字母表上一些特殊形式的字符串的集合,是正则式所表示的集

12、合.n正则式：用类似代数表达式的方法表示正则语言。n运算:作用于语言上的三种代数运算n联合联合（union）n连接连接（concatenation）n（星）（星）闭包闭包（closure）n 第16页，本讲稿共38页172022/10/21College of Computer Science&Technology,BUPT正则表达式（regular expression）n 归纳定义正则表达式如下：基础基础：，a（a T）都是正则式）都是正则式(原子正则式原子正则式)，相应的正则集为相应的正则集为，a归纳：归纳：如果如果A和和B是正则式，且分别代表集合是正则式，且分别代表集合L(A)和和L(

13、B)，则则(A+B)，(A.B),A*也是正则式，分别表示以下正则集也是正则式，分别表示以下正则集.L(A)L(B)(语言语言A/语言语言B的串的串)L(A).L(B)(两个语言中的串的连接两个语言中的串的连接)L(A)*(语言语言A中的串的多次连接中的串的多次连接)n 仅通过有限次使用以上两步定义的表达式，才是字母表T上的正则式。这些正则式所表示的字符串集合是T上的正则集。第17页，本讲稿共38页182022/10/21College of Computer Science&Technology,BUPT正则表达式算符优先级n算符优先级（算符优先级（precedence）依次为）依次为n（c

14、losure）n连接连接（concatenation）n（union）定义：若两个正则式表示相同的正则集，则称这两个正则式相等。即 R1R2 L(R1)=L(R2)注1：正则集是T*的子集。注2：L+包含当且仅当L包含。注3：每个正则集至少对应一个正则式（可有无穷多个正则式）第18页，本讲稿共38页192022/10/21College of Computer Science&Technology,BUPT正则表达式举例n书p76 例1 n表示如下语言的正则表达式：语言中的每个字符串由交替的 0s 和 1s 构成n(01)*+(10)*+0(10)*+1(01)*n(+1)(01)*(+0)n

15、(+0)(10)*(+1)第19页，本讲稿共38页202022/10/21College of Computer Science&Technology,BUPT语言的联合（union）运算n 两个语言 L 和 M 的联合n L M=w w L w M n 举例 设 L=001,10,111,M=,001,则 L M=,10,001,111 第20页，本讲稿共38页212022/10/21College of Computer Science&Technology,BUPT语言的连接（concatenation）运算n 两个语言两个语言L 和和M 的的连接连接nL M=w1w2 w1 L w2

16、M n有时记有时记L M 为为LM n举例举例设设L=001,10,111,M=,001,则则 LM=001,10,111,001001,10001,111001 第21页，本讲稿共38页222022/10/21College of Computer Science&Technology,BUPT语言的闭包（closure）运算n语言语言L 的闭包的闭包nL*=wn w L n 0,其中其中wn 为为w 的的n 次连次连接接或或L*=L0 L1 L2 =i 0Li,其中其中L0=，L1=L,L2=LL,n举例举例设设L=0,11,则则 L*=,0,11,00,011,110,1111,000,

17、0011,0110,01111,1100,11011,11110,111111,第22页，本讲稿共38页232022/10/21College of Computer Science&Technology,BUPT正则式的性质交换律（交换律（commutativity）和结合律）和结合律（associativeity）n(1)(+)+(+)n(2)()()n(3)+等幂律（等幂律（idempotent law）n(4)+分配律（分配律（distributive law）n(5)(+)+n(6)(+)+第23页，本讲稿共38页242022/10/21College of Computer Sci

18、ence&Technology,BUPT正则式的性质幺元（幺元（identities）和零元（）和零元（annihilators）n(7)+n(8)n(9)与闭包相关的定律与闭包相关的定律n(10)(*)*n(11)*+*n*=n*=nL+=LL*=L*L （L+的定义）的定义）nL*=L+第24页，本讲稿共38页252022/10/21College of Computer Science&Technology,BUPT正则式的性质(11)*+*证明：证明：*2n L(*)L()L(2)L(n)L(+*)L()(L()L(2)L(n)L()L(*)而而 L()L(*)+*第25页，本讲稿共3

19、8页262022/10/21College of Computer Science&Technology,BUPT右线性文法与正则式 n 右(左)线性文法又称为正则文法，右线性文法与正则式可以用来代表同一正则语言。二者具有等效性。n n例：文法 S aS，S an对应正则式：对应正则式：a+，或者，或者a*a第26页，本讲稿共38页272022/10/21College of Computer Science&Technology,BUPT从右线性文法导出正则式求解规则求解规则:n设设x=x+，T*，(NT)*,x Nn则则x的解为的解为x*证明：证明：x=x+表示表示x有两个生成式有两个生成

20、式:xx和和x，生成的语言为（生成的语言为（，,）,显然该显然该语言可用正则式语言可用正则式*表示。表示。书书p78，例例2书书p79，例例3第27页，本讲稿共38页282022/10/21College of Computer Science&Technology,BUPT第六节 正则集和右线性文法n 正则集是由右线性文法产生的语言n 由右线性文法产生的语言都是正则集(一).求证正则集是由右线性文法产生的语言证明方法：找出相应的右线性文法，使之产生的语言是这些正则集。第28页，本讲稿共38页292022/10/21College of Computer Science&Technology,

21、BUPT1.首首先先从从最最简简单单的的正正则则式式出出发发，求求证证其其正正则则集集，a是右线性语言。是右线性语言。证明证明:对正则集对正则集，有右线性文法有右线性文法GS，T，S，使使L(G)=对正则集对正则集,有右线性文法有右线性文法GS，T，S-，S，使，使L(G)=对正则集对正则集a，有右线性文法有右线性文法GS，T，S-a，S，使，使L(G)=a 第29页，本讲稿共38页302022/10/21College of Computer Science&Technology,BUPT2.将将对对由由并并，积积，闭闭包包形形成成的的正正则则集集的的证证明明，改改为为对对右线性语言的证明。

22、右线性语言的证明。设设在在字字母母表表T上上，有有语语言言L1和和L2，则则L1 L2，L1.L2，L1*都是右线性语言。都是右线性语言。证明方法：证明方法：分别找出相应的右线性文法。分别找出相应的右线性文法。设设G1（N1，T，P1，S1）产生）产生L1G2（N2，T，P2，S2）产生）产生L2N1 N2(若不为空若不为空,则可对则可对N中符号换名中符号换名)第30页，本讲稿共38页312022/10/21College of Computer Science&Technology,BUPT构造构造G（N，T，P，S）产生）产生L，使，使L=L1 L2其中其中NN1 N2 S,S为新的非终结

23、符；为新的非终结符；PP1 P2 SS1，SS2先证先证L L1 L2：在在G中中，由由G的的定定义义，对对于于任任意意，意意味味着着或或者者（按按G1的的产产生生式式），或或者者（按按G2的的产生式）产生式）即文法即文法G的每个句子或由的每个句子或由G1产生，或由产生，或由G2产生。产生。L(G)L(G1)L(G2)再证再证L1 L2 L：设有设有 L1 L2，则存在推导，则存在推导S1G1+或或S2G2+必必有有SG+。即即L1 L2 L。命命题题得得证证(a).求证求证L1 L2是右线性语言是右线性语言第31页，本讲稿共38页322022/10/21College of Computer

24、 Science&Technology,BUPT构造构造G（N，T，P，S）其中其中NN1UN2，SS1，生成式生成式P为为:若若A-B P1，则它也属于，则它也属于P若若A-P1，则，则A-S2 PP2 P先证先证L(G1).L(G2)L(G)若有任意若有任意S1*1与与S2*2分别属于分别属于G1和和G2定义的语言中，定义的语言中，那么有那么有S11A2B3C1和和S21A12B23C32，SS11A2B3C1.S2*1.2 L(G1).L(G2)L(G)(b).求证L1L2是右线性语言第32页，本讲稿共38页332022/10/21College of Computer Science&

25、Technology,BUPT再证再证L(G)L(G1).L(G2)若有若有SS11A2B3C1.S2*1.2那么则必然在那么则必然在G1和和G2中同时有中同时有S11A2B3C1和和S21A12B23C32 L(G)L(G1).L(G2)命题得证命题得证(b).求证L1.L2是右线性语言第33页，本讲稿共38页342022/10/21College of Computer Science&Technology,BUPT证明证明:构造构造G（N，T，P，S）其中；其中；NN1US，S N1，S是一个新的非终结符，是一个新的非终结符，生成式生成式P为为:如果如果A-B P1，则，则A-BP。如果

26、如果A-P1，则，则A-SPS-S1，S-P。先证先证L(G)L(G1)*若有若有SS11S*12S*12i.S12i则在则在G1中必然有中必然有S1*1；S1*2；。；。；S1*i L(G)L(G1)*(c).求证L1*是右线性语言第34页，本讲稿共38页352022/10/21College of Computer Science&Technology,BUPT再证再证L(G1)*L(G)若若G1中有中有S1*1；S1*2；。；。；S1*i则在则在G中必然有中必然有SS11S*12S*12i.S12i L(G1)*L(G)因此因此L*可以用右线性文法描述。可以用右线性文法描述。证毕证毕(c

27、).求证L1*是右线性语言(续)第35页，本讲稿共38页362022/10/21College of Computer Science&Technology,BUPT思路：思路：由给定的右线性文法可找出正则式，而正则式表示由给定的右线性文法可找出正则式，而正则式表示的语言即为正则集。的语言即为正则集。方法：方法：对右线性文法构造标准形式的正规表达式方程组，对右线性文法构造标准形式的正规表达式方程组，应用规则应用规则xx+x*进行消元，进行消元，求解方程组，即可得出正规表达式。求解方程组，即可得出正规表达式。由由(一一)和和(二二)即可得出下定理即可得出下定理:定理定理:一个语言是正则集，当且仅

28、当该语言为右线性一个语言是正则集，当且仅当该语言为右线性语言。语言。(二).证明由右线性文法产生的语言是正则集第36页，本讲稿共38页372022/10/21College of Computer Science&Technology,BUPT课堂练习 n Exercise 对于以上自动机，已经求出其语言的一个正规表 达式如下 (0+1)*1(0+1)+(0+1)*1(0+1)(0+1)n 使用分配律求出两种不同的更简单的与之等价的表达式.n 参考结果参考结果 （1）(0+1)*1(+0+1)(0+1)（2)(0+1)*1(0+1)(+0+1)第37页，本讲稿共38页382022/10/21College of Computer Science&Technology,BUPT课后练习 chap3 习题 习题4，习题15第38页，本讲稿共38页