形式语言基础 .ppt
《形式语言基础 .ppt》由会员分享,可在线阅读,更多相关《形式语言基础 .ppt(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、形式语言基础 现在学习的是第1页,共19页 第第 2 2 章章 形式语言基础形式语言基础 计算机处理语言,首先应考虑语言的形式化、规计算机处理语言,首先应考虑语言的形式化、规范化,使其具有可计算性和可操作性;这就是形式语范化,使其具有可计算性和可操作性;这就是形式语言理论研究的问题。言理论研究的问题。形式语言诞生于形式语言诞生于19561956年,由年,由chomskychomsky创立。通常,创立。通常,语言研究至少涉及三个方面:语言研究至少涉及三个方面:语法语法、语义语义和和语用语用;这里仅侧重于这里仅侧重于语法的研究语法的研究。形式语言的形式语言的基本观点基本观点是是 :语言是符号串之集
2、合!语言是符号串之集合!形式语言理论研究的形式语言理论研究的基本问题基本问题是:是:研究符号串集合的表示方法、结构特性研究符号串集合的表示方法、结构特性以及运算规律。以及运算规律。【前前 言言】现在学习的是第2页,共19页【内容提要内容提要】第第 2 2 章章 形式语言基础形式语言基础 2.12.1 形式语言是形式语言是符号串集合符号串集合 2.22.2 形式语言是由形式语言是由文法定义文法定义的的 2.32.3 主要主要语法成分语法成分的定义的定义 2.42.4 两类两类特性文法特性文法 2.5 2.5 文法变换文法变换方法方法 2.6 2.6 关于关于形式语言的分类形式语言的分类问题问题现
3、在学习的是第3页,共19页 字母表字母表 -元素元素(符号符号)的非空有限集合;的非空有限集合;符号串符号串 -符号的有限序列;符号的有限序列;符号串集合符号串集合 -有限个或者无限个符号串组成有限个或者无限个符号串组成的集合;的集合;规规 则则 -以某种形式表达的在一定范围内共以某种形式表达的在一定范围内共同遵守的章程和制度;这里,指符号串的组成同遵守的章程和制度;这里,指符号串的组成规则。规则。2.1 2.1 形式语言是符号串集合形式语言是符号串集合 【形式语言形式语言】是是字母表字母表上的符号,按一定的上的符号,按一定的规则规则组成的所有组成的所有符号串集合符号串集合;其中的每个符号串;
4、其中的每个符号串称为称为句子句子。【名词解释名词解释】:三要素!现在学习的是第4页,共19页【例例2.12.1】L L1 1=00,01,10,11;=00,01,10,11;字母表字母表1 1=0,1,=0,1,句子有:句子有:00,01,10,1100,01,10,11【注注】b b0 0=(epsilonepsilon空符号串)空符号串),b,b1 1=b,b=b,b2 2=bb,b=bb,b3 3=bbb,=bbb,L L1 1 为有限语言为有限语言;L;L2 2 为无限语言。为无限语言。形式语言概念示例:形式语言概念示例:【例例2.22.2】L L2 2=ab=abm mc,bc,b
5、n n|m0,n0|m0,n0 字母表字母表2 2=a,b,c,=a,b,c,句型句型1:ab1:abm mc,c,有句子:有句子:abc,abbc,abbbc,abc,abbc,abbbc,句型句型2:b2:bn n ;有句子:有句子:,b,bb,bbb,b,bb,bbb,两个语言!现在学习的是第5页,共19页1.1.连接连接:.=如如 a.b=aba.b=ab 2.1.1 2.1.1 符号串符号串(集合集合)的运算的运算3.3.方幂方幂:n n=n-1n-1=n-1n-1 4.4.闭包:闭包:n n个个.符号串的运算符号串的运算 设设 ,为两个符号串,则为两个符号串,则:的正闭包:的正闭包
6、:+=1 1|2 2|n n|的星闭包:的星闭包:*=0 0|1 1|2 2|n n|0 0=(空符号串空符号串)什麽符号也没有的符号串什麽符号也没有的符号串 !1 1=;2 2=;2.2.或或:|=(或者或者 )这是一种泛指!现在学习的是第6页,共19页2.1.1 2.1.1 符号串符号串(集合集合)的运算的运算(续续1)1)【例例】:ab|cd=abab|cd=ab(或者或者 cd cd)abc.de=abcdeabc.de=abcde (a|b)(a|b)1 1=(a|b)=a|b =(a|b)=a|b (a|b)(a|b)*=(a|b)=(a|b)0 0|(a|b)|(a|b)1 1|
7、(a|b)|(a|b)2 2|(a|b)(a|b)2 2=(a|b)(a|b)=aa|ab|ba|bb=(a|b)(a|b)=aa|ab|ba|bb 即:即:(a|b)(a|b)*=(a|b)=(a|b)n n,n0n0同理:同理:(a|b)(a|b)+=(a|b)=(a|b)n n,n n0 0 符号串运算示例符号串运算示例泛指:由a,b组成的任意符号串!(包括空串)现在学习的是第7页,共19页1.1.乘积:乘积:AB=xy|xAB=xy|x A A 且且 y y BB 2.1.1 2.1.1 符号串符号串(集合集合)的运算的运算(续续2)2)4.4.闭包:闭包:A A 的正闭包的正闭包:A
8、 A+=A=A1 1AA2 2AAn nA A 的星闭包的星闭包:A A*=A=A0 0AA1 1AA2 2AAn n设设 A A 和和 B B 为两个符号串集合,则:为两个符号串集合,则:2.2.和:和:AB=A+B=x|xAB=A+B=x|x A A 或或 x x BB 3.3.方幂:方幂:A An n=AA=AAA=AAA=AAn-1n-1=A=An-1n-1A An n个个A A0 0=;A A1 1=A=A;A A2 2=AA;A=AA;A3 3=AAA;=AAA;.符号串集合的运算符号串集合的运算 现在学习的是第8页,共19页 符号串集合运算示例:符号串集合运算示例:【例例2.32
9、.3】设设 A=a,b,B=c,dA=a,b,B=c,d 则则 A+B=a,b,c,d A+B=a,b,c,d 则则 AB=xy|xAB=xy|x A,yA,y B=B=ac,ad,bc,bdac,ad,bc,bd【例例2.42.4】设设 A=aA=a 则则 A A*=A=A0 0AA1 1AA2 2AAn n =+a+aa+aaa+a+aa+aaa+=,a,aa,aaa,a,aa,aaa,=a =an n|n0|n0 现在学习的是第9页,共19页【例例2.52.5】设设 A=aA=a,bb,A A*=?=?A A*=A=A0 0AA1 1AA2 2AAn n A A0 0=;A A1 1=A
10、=a=A=a,b;b;A A2 2=A.A=a=A.A=a,b.ab.a,b=aa,ab,ba,bb;b=aa,ab,ba,bb;A A3 3=A.A=A.A2 2=a=a,b.aa,ab,ba,bbb.aa,ab,ba,bb =aaa,aab,aba,abb,baa,bab,bba,bbb;=aaa,aab,aba,abb,baa,bab,bba,bbb;A A*=x|x=(a|b)=x|x=(a|b)n n ,n0 n0 符号串集合运算示例符号串集合运算示例(续续):推论推论:若:若 A A为任一字母表为任一字母表,则则 A A*就是该字母就是该字母表上表上的所有符号串的所有符号串(包括空
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言基础 形式语言 基础
限制150内