形式语言与自动机理论电子教案-01.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,形式语言与自动机理论,Formal Languages and Automata Theory,张军,2026/1/31 周六,1,课程目的和基本要求,课程性质,技术基础,基础知识要求,数学分析（或者高等数学），离散数学,主要特点,抽象和形式化,理论证明和构造性,基本模型的建立与性质,1/31/2026,2,课程目的和基本要求,本专业人员4种基本的专业能力,计算思维能力,算法的设计与分析能力,程序设计和实现能力,计算机软硬件系统的认知、分析、设计与应用能力,计算思维能力,逻辑思维能力和抽象思维能力,构造模型对问题进行形式化描述,理解和处理形式模型,1/31/2026,3,课程目的和基本要求,知识,掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。,能力,培养学生的形式化描述和抽象思维能力。,使学生了解和初步掌握,“,问题、形式化描述、自动化（计算机化）,”,这一最典型的计算机问题求解思路。,1/31/2026,4,主要内容,语言的,文法,描述。,RL,RG、FA、RE、RL,的性质,。,CFL,CFG(CNF、GNF)、PDA、CFL,的性质。,TM,基本TM、构造技术、TM的修改。,CSL,CSG、LBA。,1/31/2026,5,第1章,绪论,1.4 语言,1.41 什么是语言,例如：,“,学大一生是个我,”,；,“,我是一个大学生,”,。,语言是一定的群体用来进行交流的工具。,必须有着一系列的生成规则、理解,(,语义,),规则,。,1/31/2026,6,1.4.1 什么是语言,1/31/2026,7,1.4.1 什么是语言,斯大林：从强调语言的作用出发，把语言定义为,“,为广大的人群所理解的字和组合这些字的方法,”,。,语言学家韦波斯特,(Webster),：为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。,要想对语言的性质进行研究，用这些定义来建立语言的数学模型是不够精确的。必须有更形式化的定义。,1/31/2026,8,1.4.2 形式语言与自动机理论的产生与作用,语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言的角度研究语言。,1956,年，他将语言,L,定义为一个字母表中的字母组成的一些串的集合：,L,*,。,字母表上按照一定的规则定义一个文法,(grammar),，该文法所能产生的所有句子组成的集合就是该文法产生的语言。,1959,年，乔姆斯基根据产生语言文法的特性，将语言划分成,3,大类。,1/31/2026,9,1.4.2 形式语言与自动机理论的产生与作用,1951,年到,1956,年，克林,(Kleene),在研究神经细胞中，建立了识别语言的系统,有穷状态自动机。,1959,年，乔姆斯基发现文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性，这一成果被认为是将形式语言置于了数学的光芒之下，使得形式语言真正诞生了。,1/31/2026,10,1.4.2 形式语言与自动机理论的产生与作用,20,世纪,50,年代，巴科斯范式,(Backus Nour Form,或,Backus Normal Form,，,BNF),实现了对高级语言,ALGOL-60,的成功描述。这一成功，使得形式语言在,20,世纪,60,年代得到了大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。,相应的理论用于其他方面。,1/31/2026,11,14.2 形式语言与自动机理论的产生与作用,形式语言与自动机理论在计算机科学与技术学科的人才的计算思维的培养中占有极其重要的地位。,计算学科的主题：,“,什么能被有效地自动化,”,。,1/31/2026,12,1.4.2 形式语言与自动机理论的产生与作用,计算机科学与技术学科人才专业能力构成,“,计算思维能力,”,抽象思维能力、逻辑思维能力。,算法设计与分析能力。,程序设计与实现能力。,计算机系统的认知、分析、设计和应用能力。,1/31/2026,13,1.4.2 形式语言与自动机理论的产生与作用,1/31/2026,14,1.4.2 形式语言与自动机理论的产生与作用,考虑的对象的不同，所需要的思维方式和能力就不同，通过这一系统的教育，在不断升华的过程中，逐渐地培养出了学生的抽象思维能力和对逻辑思维方法的掌握。,创新意识的建立和创新能力的培养也在这个教育过程中循序渐进地进行着。,内容用于后续课程和今后的研究工作。,是进行思维训练的最佳知识载体。,是一个优秀的计算机科学工作者必修的一门课程。,1/31/2026,15,1.4.3 基本概念,对语言研究的三个方面,表示,(representation),无穷语言的表示。,有穷描述,(finite description),研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。,结构,(structure),语言的结构特征。,1/31/2026,16,1.4.3 基本概念,字母表,(alphabet),字母表,是一个非空有穷集合，字母表中的元素称为该字母表的一个,字母,(letter),。又叫做,符号,(symbol),、或者,字符,(character)。,非空性。,有穷性。,例如：,a，b，c，d,a，b，c，z,0,1,1/31/2026,17,1.4.3 基本概念,字符的两个特性,整体性,(monolith),，也叫不可分性。,可辨认性,(distinguishable),，也叫可区分性。,例（续）,a，a，b，b,aa，ab，bb,，,1/31/2026,18,1.4.3 基本概念,字母表的乘积,(product),1,2,=ab|a,1,，,b,2,例如：,0,10,1=00,，,01,，,10,，,00,0,1a,，,b,，,c,，,d=0a,，,0b,，,0c,，,0d,，,1a,，,1b,，,1c,，,1d,a,，,b,，,c,，,d0,1=a0,，,a1,，,b0,，,b1,，,c0,，,c1,，,d0,，,d1,aa,，,ab,，,bb0,1=aa0,，,aa1,，,ab0,，,ab1,，,bb0,，,bb1,1/31/2026,19,1.4.3 基本概念,字母表的,n,次,幂,0,=,n,=,n-1,是由中的,0,个字符组成的。,的,正闭包,+,=,2,3,4,的,克林闭包,*,=,0,+,=,0,2,3,1/31/2026,20,1.4.3 基本概念,例如：,0,1,+,=0,，,1,，,00,，,01,，,11,，,000,，,001,，,010,，,011,，,100,，,0,1,*,=,，,0,，,1,，,00,，,01,，,11,，,000,，,001,，,010,，,011,，,100,，,a,，,b,，,c,，,d,+,=a,，,b,，,c,，,d,，,aa,，,ab,，,ac,，,ad,，,ba,，,bb,，,bc,，,bd,，,aaa,，,aab,，,aac,，,aad,，,aba,，,abb,，,abc，,a,，,b,，,c,，,d,*a,，,b,，,c,，,d,，,aa,，,ab,，,ac,，,ad,，,ba,，,bb,，,bc,，,bd,，,aaa,，,aab,，,aac,，,aad,，,aba,，,abb,，,abc,1/31/2026,21,1.4.3 基本概念,结论：,*,=x|x是中的若干个，包括0个字符，连接而成的一个字符串。,+,=x|x是中的至少一个字符连接而成的字符串。,1/31/2026,22,1.4.3 基本概念,句子(sentence),是一个字母表，,x,*,，x叫做上的一个,句子。,句子相等。,两个句子被称为相等的，如果它们对应位置上的字符都对应相等。,别称,字(word)、(字符、符号)行(line)、(字符、符号)串(string)。,1/31/2026,23,1.4.3 基本概念,出现,(apperance),x，y,*,，a，句子xay中的a叫做a在该句子中的一个,出现。,当x=时，a的这个出现为字符串xay的首字符,如果a的这个出现是字符串xay的第n个字符，则y的首字符的这个出现是字符串xay的第n+1个字符。,当y=时，a的这个出现是字符串xay的尾字符,例：abaabb。,1/31/2026,24,1.4.3 基本概念,句子的长度,(length),x,*,，句子,x,中字符出现的总个数叫做该,句子的长度,，记作,|x|。,长度为,0,的字符串叫,空句子,，记作。,例如：,|abaabb|=6,|bbaa|=4,|,|=0,|bbabaabbbaa|=11,1/31/2026,25,1.4.3 基本概念,注意事项,是一个句子。,。这是因为不是一个空集，它是含有一个空句子的集合。|=1，而|,|=0。,1/31/2026,26,1.4.3 基本概念,并置(concatenation),x，y,*,，x，y的,并置,是由串x直接相接串y所组成的。记作xy。并置又叫做,连结。,串x的n次,幂,x,0,=,x,n,=x,n-1,x,1/31/2026,27,1.4.3 基本概念,例,如：,对x=001，y=1101,x,0,=y,0,=,x,4,=001001001001,y,4,=1101110111011101,对x=0101，y=110110,x,2,=01010101,y,2,=110110110110,x,4,=0101010101010101,y,4,=110110110110110110110110,1/31/2026,28,1.4.3 基本概念,*,上的并置运算性质,结合律：(xy)z=x(yz)。,左消去律：如果xy=xz，则y=z。,右消去律：如果yx=zx，则y=z。,惟一分解性：存在惟一确定的a,1,，a,2,，a,n,，使得x=a,1,a,2,a,n。,单位元素：x=x=x。,1/31/2026,29,1.4.3 基本概念,前缀与后缀,设x，y，z，w，v*，且x=yz，w=yv,(1)y是x的前缀(prefix)。,(2)如果z，则y是x的真前缀(proper prefix)。,(3)z是x的后缀(suffix)；,(4)如果y，则z是x的真后缀(proper suffix)。,(5)y是x和w的公共前缀(common Prefix)。,1/31/2026,30,1.4.3 基本概念,公共,前缀与后缀,(6)如果x和w的任何公共前缀都是y的前缀，则y是x和w的最大公共前缀。,(7)如果x=zy，w=vy，则y是x和w的公共后缀(common suffix)。,(8)如果x和w的任何公共后缀都是y的后缀，则y是x和w的最大公共后缀。,1/31/2026,31,1.4.3 基本概念,例,字母表=a，b上的句子abaabb的前缀、后缀、真前缀和真后缀如下：,前缀：，a，ab，aba，abaa，abaab，abaabb,真前缀：，a，ab，aba，abaa，abaab,后缀：，b，bb，abb，aabb，baabb，abaabb,真后缀：，b，bb，abb，aabb，baabb,1/31/2026,32,1.4.3 基本概念,结论,x,的任意前缀,y,有惟一的一个后缀,z,与之对应，使得,x=yz,；反之亦然。,x,的任意真前缀,y,有惟一的一个真后缀,z,与之对应，使得,x=yz,；反之亦然。,|w|w,是,x,的后缀,|=|w|w,是,x,的前缀,|,。,|w|w,是,x,的真后缀,|=|w|w,是,x,的真前缀,|,。,w|w,是,x,的前缀,=w|w,是,x,的真前缀,x,，,|w|w,是,x,的前缀,|=|w|w,是,x,的真前缀,|+1。,1/31/2026,33,1.4.3 基本概念,结论,w|w,是,x,的后缀,=w|w,是,x,的真后缀,x,，,|w|w,是,x,的后缀,|=|w|w,是,x,的真后缀,|+1,。,对于任意字符串,w,，,w,是自身的前缀，但不是自身的真前缀；,w,是自身的后缀，但不是自身的真后缀。,对于任意字符串,w,，是,w,的前缀，且是,w,的真前缀；是,w,的后缀，且是,w,的真后缀,1/31/2026,34,1.4.3 基本概念,约定,用小写字母表中较为靠前的字母a，b，c，表示字母表中的字母。,用小写字母表中较为靠后的字母x，y，z，表示字母表上的句子。,用x,T,表示x的倒序。例如，如果x=abc，则x,T,=cba。,1/31/2026,35,1.4.3 基本概念,子串(substring),w，x，y，z,*,，且w=xyz，则称y是w的,子串。,公共子串(common substring),t，u，v，w，x，y，z,*,，且t=uyv，w=xyz，则称y是t和w的,公共子串(common substring),。如果y,1,，y,2,，y,n,是t和w的公共子串，且max|y,1,|，|y,2,|，|y,n,|=|y,j,|，则称y,j,是t和w的,最大公共子串。,两个串的最大公共子串并不一定是惟一的。,1/31/2026,36,1.4.3 基本概念,语言(language),L,*,，L称为字母表上的一个,语言(language),，,xL，x叫做L的一个句子。,例：0，1上的不同语言,00，11，0，1,0，1，00，11，0，1，00，11，01，10,00，11,*,，01，10,*,，00，01，10，11,*,，,00，1,*,1，0，1,*,1110，1,*,1/31/2026,37,1.4.3 基本概念,语言的,乘积(product),L,1,1,*,，L,2,2,*,，语言L,1,与L,2,的,乘积,是一个语言，该语言定义为：,L,1,L,2,=xy|xL,1,，yL,2,是字母表,1,2,上的语言。,1/31/2026,38,1.4.3 基本概念,例,L,1,=0,，,1。,L,2,=00,，,01,，,10,，,11。,L,3,=0,，,1,，,00,，,01,，,10,，,11,，,000,，,=,+,。,L,4,=,，,0,，,1,，,00,，,01,，,10,，,11,，,000,，,=,*,。,L,5,=0,n,|n,1。,L,6,=0,n,1,n,|n,1。,L,71,n,|n,1。,L,8,=0,n,1,m,|n,，,m,1。,L,9,=0,n,1,n,0,n,|n,1。,L,10,=0,n,1,m,0,k,|n,，,m,，,k,1。,L,11,=x|x,+,且,x,中,0,和,1,的个数相同,。,1/31/2026,39,1.4.3 基本概念,上述几个语言的部分特点及相互关系,上述所有语言都是,L,4,的子集,(,子语言,),；,L,1,，,L,2,是有穷语言；其他为无穷语言；其中,L,1,是上的所有长度为,1,的句子组成的语言，,L,2,是上的所有长度为,2,的句子组成的语言；,L,3,，,L,4,分别是的正闭包和克林闭包；,L,5,L,7,L6,，但,L,5,L,7,=L,8,；同样,L,9,L,10,，但是我们有：,L,6,L,5,L,7,，,L,9,L,10。,1/31/2026,40,1.4.3 基本概念,L,6,=0,n,1,n,|n,1,中的句子中的,0,和,1,的个数是相同的，并且所有的,0,在所有的,1,的前面，,L,11,=x|x,+,且,x,中,0,和,1,的个数相同,中的句子中虽然保持着,0,的个数和,1,的个数相等，但它并没要求所有的,0,在所有的,1,的前面。例如，,0101,，,1100,L,11,，但是,0101,L,6,，,1100,L,6,。而对,x,L,6,，有,x,L,11,。所以，,L,6,L,11。,1/31/2026,41,1.4.3 基本概念,L,1,L,12,，,L,2,L,12,L,5,L,12,，,L,6,L,12,L,7,L,12,，,L,8,L,12,L,9,L,12,，,L,10,L,12,L,1,L,10,，,L,2,L,10,L,5,L,10,，,L,6,L,10,L,7,L,10,，,L,8,L,10,L,9,L,10,，,L,10,L,12,1/31/2026,42,1.4.3 基本概念,例,x|x=x,T,，,x,。,xx,T,|x,+,。,xx,T,|x,*,。,xwx,T,|x,，,w,+,。,xx,T,w|x,，,w,+,。,1/31/2026,43,1.4.3 基本概念,幂,L,*,，L的n次,幂,是一个语言，该语言定义为,当,n=0,是，,L,n,=,。,当,n,1,时，,L,n,=L,n-1,L,。,正闭包,L,+,=L,L,2,L,3,L,4,克林闭包,L,*,=L,0,L,L,2,L,3,L,4,1/31/2026,44,1.5 小结,本章简单叙述了一些基础知识，一方面，希望读者通过对本章的阅读，熟悉集合、关系、图、形式语言等相关的一些基本知识点，为以后各章学习作适当的准备。另一方面，也使读者熟悉本书中一些符号的意义。,1/31/2026,45,1.5 小结,(1),集合：集合的表示、集合之间的关系、集合的基本运算。,(2),关系：主要介绍了二元关系相关的内容。包括等价关系、等价分类、关系合成、关系闭包。,(3),递归定义与归纳证明。,1/31/2026,46,1.5 小结,(4),图：无向图、有向图、树的基本概念。,(5),语言与形式语言：自然语言的描述，形式语言和自动机理论的出现，形式语言和自动机理论对计算机科学与技术学科人才能力培养的作用,(6),基本概念：字母表、字母、句子、字母表上的语言、语言的基本运算,1/31/2026,47,