形式语言与自动机理论电子教案幻灯片.ppt

形式语言与自动机理论电子教案2023/1/71第1页，共47页，编辑于2022年，星期六课程目的和基本要求课程目的和基本要求课程性质课程性质技术基础技术基础 基础知识要求基础知识要求 数学分析（或者高等数学），离散数学数学分析（或者高等数学），离散数学 主要特点主要特点 抽象和形式化抽象和形式化 理论证明和构造性理论证明和构造性 基本模型的建立与性质基本模型的建立与性质 2023/1/72第2页，共47页，编辑于2022年，星期六课程目的和基本要求课程目的和基本要求本专业人员本专业人员4 4种基本的专业能力种基本的专业能力计算思维能力计算思维能力算法的设计与分析能力算法的设计与分析能力程序设计和实现能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力计算思维能力逻辑思维能力和抽象思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述构造模型对问题进行形式化描述理解和处理形式模型理解和处理形式模型2023/1/73第3页，共47页，编辑于2022年，星期六课程目的和基本要求课程目的和基本要求 知识知识掌握正则语言、下文无关语言的文法、识别模掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。型及其基本性质、图灵机的基本知识。能力能力培养学生的形式化描述和抽象思维能力。培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握使学生了解和初步掌握“问题、形式化描述、问题、形式化描述、自动化（计算机化）自动化（计算机化）”这一最典型的计算机问这一最典型的计算机问题求解思路。题求解思路。2023/1/74第4页，共47页，编辑于2022年，星期六主要内容主要内容 语言的语言的文法文法描述。描述。RLRLRGRG、FA FA、RERE、RLRL的性质的性质 。CFLCFLCFG(CNFCFG(CNF、GNF)GNF)、PDAPDA、CFLCFL的性质。的性质。TMTM基本基本TMTM、构造技术、构造技术、TMTM的修改。的修改。CSLCSLCSGCSG、LBALBA。2023/1/75第5页，共47页，编辑于2022年，星期六第第1章章绪论绪论1.4语言语言1.4.1 1.4.1 什么是语言什么是语言 例如：例如：“学大一生是个我学大一生是个我”；“我是一我是一个大学生个大学生”。语言是一定的群体用来进行交流的工具。语言是一定的群体用来进行交流的工具。必须有着一系列的生成规则、理解必须有着一系列的生成规则、理解(语义语义)规则规则。2023/1/76第6页，共47页，编辑于2022年，星期六1.4.1什么是语言什么是语言2023/1/77第7页，共47页，编辑于2022年，星期六1.4.1什么是语言什么是语言斯大林：从强调语言的作用出发，把语言定斯大林：从强调语言的作用出发，把语言定义为义为“为广大的人群所理解的字和组合这为广大的人群所理解的字和组合这些字的方法些字的方法”。语言学家韦波斯特语言学家韦波斯特(Webster)：为相当大的：为相当大的团体的人所懂得并使用的字和组合这些字团体的人所懂得并使用的字和组合这些字的方法的统一体。的方法的统一体。要想对语言的性质进行研究，用这些定义来要想对语言的性质进行研究，用这些定义来建立语言的数学模型是不够精确的。必须建立语言的数学模型是不够精确的。必须有更形式化的定义。有更形式化的定义。2023/1/78第8页，共47页，编辑于2022年，星期六1.4.2形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用语言学家乔姆斯基，毕业于宾西法尼亚大学，语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言的角度研究语言。最初从产生语言的角度研究语言。1956年，年，他将语言他将语言L定义为一个字母表定义为一个字母表中的字母组中的字母组成的一些串的集合：成的一些串的集合：L*。字母表上按照一定的规则定义一个文法字母表上按照一定的规则定义一个文法(grammar)，该文法所能产生的所有句子组，该文法所能产生的所有句子组成的集合就是该文法产生的语言。成的集合就是该文法产生的语言。1959年，乔姆斯基根据产生语言文法的特性，年，乔姆斯基根据产生语言文法的特性，将语言划分成将语言划分成3大类。大类。2023/1/79第9页，共47页，编辑于2022年，星期六1.4.2形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用1951年到年到1956年，克林年，克林(Kleene)在研究神在研究神经细胞中，建立了识别语言的系统经细胞中，建立了识别语言的系统有有穷状态自动机。穷状态自动机。1959年，乔姆斯基发现文法和自动机分别从年，乔姆斯基发现文法和自动机分别从生成和识别的角度去表达语言，而且证明生成和识别的角度去表达语言，而且证明了文法与自动机的等价性，这一成果被认了文法与自动机的等价性，这一成果被认为是将形式语言置于了数学的光芒之下，为是将形式语言置于了数学的光芒之下，使得形式语言真正诞生了。使得形式语言真正诞生了。2023/1/710第10页，共47页，编辑于2022年，星期六1.4.2形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用20世纪世纪50年代，巴科斯范式年代，巴科斯范式(BackusNourForm或或BackusNormalForm，BNF)实现实现了对高级语言了对高级语言ALGOL-60的成功描述。这一的成功描述。这一成功，使得形式语言在成功，使得形式语言在20世纪世纪60年代得到了年代得到了大力的发展。尤其是上下文无关文法被作大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳近似为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。描述得到了较为深入的研究。相应的理论用于其他方面。相应的理论用于其他方面。2023/1/711第11页，共47页，编辑于2022年，星期六1.4.2形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用形式语言与自动机理论在计算机科学与技术形式语言与自动机理论在计算机科学与技术学科的人才的计算思维的培养中占有极其重学科的人才的计算思维的培养中占有极其重要的地位。要的地位。计算学科的主题：计算学科的主题：“什么能被有效地自动化什么能被有效地自动化”。2023/1/712第12页，共47页，编辑于2022年，星期六1.4.2形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用计算机科学与技术学科人才专业能力构成计算机科学与技术学科人才专业能力构成 “计算思维能力计算思维能力”抽象思维能力、逻辑思抽象思维能力、逻辑思维能力。维能力。算法设计与分析能力。算法设计与分析能力。程序设计与实现能力。程序设计与实现能力。计算机系统的认知、分析、设计和应用能力。计算机系统的认知、分析、设计和应用能力。2023/1/713第13页，共47页，编辑于2022年，星期六1.4.2形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用2023/1/714第14页，共47页，编辑于2022年，星期六1.4.2形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用考虑的对象的不同，所需要的思维方式和能力就不考虑的对象的不同，所需要的思维方式和能力就不同，通过这一系统的教育，在不断升华的过程中，逐同，通过这一系统的教育，在不断升华的过程中，逐渐地培养出了学生的抽象思维能力和对逻辑思维方法渐地培养出了学生的抽象思维能力和对逻辑思维方法的掌握。的掌握。创新意识的建立和创新能力的培养也在这个教育过程创新意识的建立和创新能力的培养也在这个教育过程中循序渐进地进行着。中循序渐进地进行着。内容用于后续课程和今后的研究工作。内容用于后续课程和今后的研究工作。是进行思维训练的最佳知识载体。是进行思维训练的最佳知识载体。是一个优秀的计算机科学工作者必修的一门课程。是一个优秀的计算机科学工作者必修的一门课程。2023/1/715第15页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念对语言研究的三个方面对语言研究的三个方面 表示表示(representation)无穷语言的表示。无穷语言的表示。有穷描述有穷描述(finitedescription)研究的语言研究的语言要么是有穷的，要么是可数无穷的，这里主要要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。研究可数无穷语言的有穷描述。结构结构(structure)语言的结构特征。语言的结构特征。2023/1/716第16页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念字母表字母表(alphabet)字母表字母表是一个非空有穷集合，字母表中的元素是一个非空有穷集合，字母表中的元素称为该字母表的一个称为该字母表的一个字母字母(letter)。又叫做。又叫做符符号号(symbol)、或者、或者字符字符(character)。非空性。非空性。有穷性。有穷性。例如：例如：a，b，c，da，b，c，z0,12023/1/717第17页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念字符的两个特性字符的两个特性 整体性整体性(monolith)，也叫不可分性。，也叫不可分性。可辨认性可辨认性(distinguishable)，也叫可区分性。，也叫可区分性。例（续）例（续）a，a，b，baa，ab，bb，2023/1/718第18页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念字母表的乘积字母表的乘积(product)12=ab|a1，b2 例如：例如：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 2023/1/719第19页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念字母表字母表的的n次次幂幂 0=n=n-1 是由是由中的中的0个字符组成的。个字符组成的。的的正闭包正闭包 +=234的的克林闭包克林闭包*=0+=0232023/1/720第20页，共47页，编辑于2022年，星期六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,2023/1/721第21页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念结论：结论：*=x|x是是中中的的若若干干个个，包包括括0个个字字符符，连连接接而成的一个字符串而成的一个字符串。+=x|x是是中中的的至至少少一一个个字字符符连连接接而而成成的的字字符符串串。2023/1/722第22页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念句子句子(sentence)(sentence)是一个字母表，是一个字母表，x*，x叫做叫做上的一个上的一个句子。句子。句子相等。句子相等。两个句子被称为相等的，如果它们对应位置上的字符两个句子被称为相等的，如果它们对应位置上的字符都对应相等。都对应相等。别称别称字字(word)、(字符、符号字符、符号)行行(line)、(字符、符号字符、符号)串串(string)。2023/1/723第23页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念出现出现(apperance)x，y*，a，句子，句子xay中的中的a叫做叫做a在该句在该句子中的一个子中的一个出现。出现。当当x=时，时，a的这个出现为字符串的这个出现为字符串xay的首字符的首字符如果如果a的这个出现是字符串的这个出现是字符串xay的第的第n个字符，则个字符，则y的首字符的这个出现是字符串的首字符的这个出现是字符串xay的第的第n+1个个字符。字符。当当y=时，时，a的这个出现是字符串的这个出现是字符串xay的尾字符的尾字符例：例：abaabb。2023/1/724第24页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念句子的长度句子的长度(length)(length)x x*，句子，句子x x中字符出现的总个数叫做该中字符出现的总个数叫做该句句子的长度子的长度，记作，记作|x|x|。长度为长度为0 0的字符串叫的字符串叫空句子空句子，记作，记作。例如：例如：|abaabb|=6|abaabb|=6|bbaa|=4|bbaa|=4|=0|=0|bbabaabbbaa|=11|bbabaabbbaa|=11 2023/1/725第25页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念注意事项注意事项是一个句子。是一个句子。这是因为。这是因为不是一个空集，它是不是一个空集，它是含有一个空句子含有一个空句子的集合。的集合。|=1，而，而|=0。2023/1/726第26页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念并置并置(concatenation)(concatenation)x，y*，x，y的的并置并置是由串是由串x直接相接串直接相接串y所所组成的。记作组成的。记作xy。并置又叫做。并置又叫做连结。连结。串串x的的n次次幂幂x0=xn=xn-1x 2023/1/727第27页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念例例如：如：对对x=001，y=1101x0=y0=x4=001001001001y4=1101110111011101对对x=0101，y=110110 x2=01010101y2=110110110110 x4=0101010101010101y4=1101101101101101101101102023/1/728第28页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念*上的并置运算性质上的并置运算性质结合律：结合律：(xy)z=x(yz)。左消去律：如果左消去律：如果xy=xz，则，则y=z。右消去律：如果右消去律：如果yx=zx，则，则y=z。惟惟一一分分解解性性：存存在在惟惟一一确确定定的的a1，a2，an，使得，使得x=a1a2an。单位元素：单位元素：x=x=x。2023/1/729第29页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念前缀与后缀前缀与后缀 设x，y，z，w，v*，且x=yz，w=yv(1)y是x的前缀(prefix)。(2)如果z，则y是x的真前缀(properprefix)。(3)z是x的后缀(suffix)；(4)如果y，则z是x的真后缀(propersuffix)。(5)y是x和w的公共前缀(commonPrefix)。2023/1/730第30页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念公共公共前缀与后缀前缀与后缀(6)如果x和w的任何公共前缀都是y的前缀，则y是x和w的最大公共前缀。(7)如果x=zy，w=vy，则y是x和w的公共后缀(commonsuffix)。(8)如果x和w的任何公共后缀都是y的后缀，则y是x和w的最大公共后缀。2023/1/731第31页，共47页，编辑于2022年，星期六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 2023/1/732第32页，共47页，编辑于2022年，星期六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。2023/1/733第33页，共47页，编辑于2022年，星期六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的真后缀的真后缀2023/1/734第34页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念约定约定 用用小小写写字字母母表表中中较较为为靠靠前前的的字字母母a，b，c，表示字母表中的字母。表示字母表中的字母。用用小小写写字字母母表表中中较较为为靠靠后后的的字字母母x，y，z，表示字母表上的句子。表示字母表上的句子。用用xT表示表示x的倒序。例如，如果的倒序。例如，如果x=abc，则，则xT=cba。2023/1/735第35页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念子串子串(substring)(substring)w，x，y，z*，且，且w=xyz，则称，则称y是是w的的子串。子串。公共子串公共子串(common substring)(common substring)t，u，v，w，x，y，z*，且，且t=uyv，w=xyz，则称，则称y是是t和和w的的公共子串公共子串(common substring)(common substring)。如果如果y1，y2，yn是是t和和w的公共子串，且的公共子串，且max|y1|，|y2|，|yn|=|yj|，则称，则称yj是是t和和w的的最大公共子串。最大公共子串。两个串的最大公共子串并不一定是惟一的。两个串的最大公共子串并不一定是惟一的。2023/1/736第36页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念语言语言(language)(language)L*，L称为字母表称为字母表上的一个上的一个语言语言(language)(language)，xL，x叫做叫做L的一个句子。的一个句子。例：例：0，1上的不同语言上的不同语言 00，11，0，10，1，00，11，0，1，00，11，01，1000，11*，01，10*，00，01，10，11*，00，1*1，0，1*1110，1*2023/1/737第37页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念语言的乘积乘积(product)L1 1*，L2 2*，语语言言L1与与L2的的乘乘积积是是一一个个语言，该语言定义为：语言，该语言定义为：L1L2=xy|xL1，yL2是字母表是字母表12上的语言。上的语言。2023/1/738第38页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念例例L1=0，1。L2=00，01，10，11。L3=0，1，00，01，10，11，000，=+。L4=，0，1，00，01，10，11，000，=*。L5=0n|n1。L6=0n1n|n1。L7=1n|n1。L8=0n1m|n，m1。L9=0n1n0n|n1。L10=0n1m0k|n，m，k1。L11=x|x+且且x中中0和和1的个数相同的个数相同。2023/1/739第39页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念上述几个语言的部分特点及相互关系上述几个语言的部分特点及相互关系 上述所有语言都是上述所有语言都是L4的子集的子集(子语言子语言)；L1，L2是是有有穷穷语语言言；其其他他为为无无穷穷语语言言；其其中中L1是是上上的的所所有有长长度度为为1的的句句子子组组成成的的语语言言，L2是是上上的的所有长度为所有长度为2的句子组成的语言；的句子组成的语言；L3，L4分别是分别是的正闭包和克林闭包；的正闭包和克林闭包；L5L7L6，但，但L5L7=L8；同样；同样L9L10，但是我们有：，但是我们有：L6 L5L7，L9 L10。2023/1/740第40页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念L6=0n1n|n1中中的的句句子子中中的的0和和1的的个个数数是是相相同同的的，并并且且所所有有的的0在在所所有有的的1的的前前面面，L11=x|x+且且x中中0和和1的的个个数数相相同同中中的的句句子子中中虽虽然然保保持持着着0的的个个数数和和1的的个个数数相相等等，但但它它并并没没要要求求所所有有的的0在在所所有有的的1的的前前面面。例例如如，0101，1100L11，但但是是0101 L6，1100 L6。而而对对 xL6，有有xL11。所所以以，L6 L11。2023/1/741第41页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念L1 L12，L2 L12L5 L12，L6 L12L7 L12，L8 L12L9 L12，L10 L12L1 L10，L2 L10L5 L10，L6 L10L7 L10，L8 L10L9 L10，L10 L122023/1/742第42页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念例例 x|x=xT，x。xxT|x+。xxT|x*。xwxT|x，w+。xxTw|x，w+。2023/1/743第43页，共47页，编辑于2022年，星期六1.4.3基本概念基本概念幂幂 L*，L L的的n n次次幂幂是一个语言，该语言定义为是一个语言，该语言定义为 当当n=0是，是，Ln=。当当n1时，时，Ln=Ln-1L 。正闭包正闭包 L L+=L=LL L2 2L L3 3L L4 4 克林闭包克林闭包 L L*=L=L0 0L LL L2 2L L3 3L L4 4 2023/1/744第44页，共47页，编辑于2022年，星期六1.5小结小结 本章简单叙述了一些基础知识，一本章简单叙述了一些基础知识，一方面，希望读者通过对本章的阅读，熟方面，希望读者通过对本章的阅读，熟悉集合、关系、图、形式语言等相关的悉集合、关系、图、形式语言等相关的一些基本知识点，为以后各章学习作适一些基本知识点，为以后各章学习作适当的准备。另一方面，也使读者熟悉本当的准备。另一方面，也使读者熟悉本书中一些符号的意义。书中一些符号的意义。2023/1/745第45页，共47页，编辑于2022年，星期六1.5小结小结(1)集集合合：集集合合的的表表示示、集集合合之之间间的的关关系系、集合的基本运算。集合的基本运算。(2)关关系系：主主要要介介绍绍了了二二元元关关系系相相关关的的内内容容。包包括括等等价价关关系系、等等价价分分类类、关关系系合合成成、关关系闭包。系闭包。(3)递归定义与归纳证明。递归定义与归纳证明。2023/1/746第46页，共47页，编辑于2022年，星期六1.5小结小结(4)图：无向图、有向图、树的基本概念。图：无向图、有向图、树的基本概念。(5)语语言言与与形形式式语语言言：自自然然语语言言的的描描述述，形形式式语语言言和和自自动动机机理理论论的的出出现现，形形式式语语言言和和自自动动机机理理论论对对计计算算机机科科学学与与技技术术学学科科人人才才能力培养的作用能力培养的作用(6)基基本本概概念念：字字母母表表、字字母母、句句子子、字字母母表上的语言、语言的基本运算表上的语言、语言的基本运算2023/1/747第47页，共47页，编辑于2022年，星期六