形式语言与自动化理论-第一章绪论20160919剖析.ppt

1.4.3 基本概念 * * 上述几个语言的部分特点及相互关系 上述所有语言都是L4的子集(子语言)； L1，L2是有穷语言；其他为无穷语言；其中L1是∑上的所有长度为1的句子组成的语言，L2是∑上的所有长度为2的句子组成的语言； L3，L4分别是∑的正闭包和克林闭包； L5L7≠L6，但L5L7= L8；同样L9≠L10，但是我们有：L6?L5L7，L9?L10。 1.4.3 基本概念 * * L6={0n1n|n≥1}中的句子中的0和1的个数是相同的，并且所有的0在所有的1的前面，L11={x|x∈∑+且x中0和1的个数相同}中的句子中虽然保持着0的个数和1的个数相等，但它并没要求所有的0在所有的1的前面。例如，0101，1100∈L11，但是0101? L6，1100?L6。而对?x∈L6，有x∈L11。所以，L6 ?L11。 1.4.3 基本概念 * * L1?L12，L2?L12 L5?L12，L6?L12 L7?L12， L8?L12 L9?L12， L10?L12 L1?L10， L2?L10 L5?L10， L6?L10 L7?L10， L8?L10 L9?L10， L10?L12 1.4.3 基本概念 * * 例 ⑴ {x|x=xT，x∈∑}。 ⑵ {xxT|x∈∑+}。 ⑶ {xxT|x∈∑*}。 ⑷ {xwxT|x，w∈∑+}。 ⑸ {xxTw|x，w∈∑+}。 1.4.3 基本概念 * * 幂 ?L?∑*，L的n次幂是一个语言，该语言定义为 ⑴ 当n=0是，Ln={ε}。 ⑵ 当n≥1时，Ln= Ln-1L 。 正闭包 L+=L∪L2∪L3∪L4∪… 克林闭包 L*= L0∪L∪L2∪L3∪L4∪… 1.5 小结 * * 本章简单叙述了一些基础知识，一方面，希望读者通过对本章的阅读，熟悉集合、关系、图、形式语言等相关的一些基本知识点，为以后各章学习作适当的准备。另一方面，也使读者熟悉本书中一些符号的意义。 1.5 小结 * * (1)? 集合：集合的表示、集合之间的关系、集合的基本运算。 (2)? 关系：主要介绍了二元关系相关的内容。包括等价关系、等价分类、关系合成、关系闭包。 (3)? 递归定义与归纳证明。 1.5 小结 * * (4)? 图：无向图、有向图、树的基本概念。 (5)? 语言与形式语言：自然语言的描述，形式语言和自动机理论的出现，形式语言和自动机理论对计算机科学与技术学科人才能力培养的作用 (6)? 基本概念：字母表、字母、句子、字母表上的语言、语言的基本运算 RL：正则语言， CFL：上下文无关语言，TM：图灵机，CSL：上下文有关语言，FA：有穷自动机，PDA：下推自动机 * （2），（3）|| 集合元素的个数，基数，势。 * * 1.4.1 什么是语言 * * 斯大林：从强调语言的作用出发，把语言定义为“为广大的人群所理解的字和组合这些字的方法”。 语言学家韦波斯特(Webster) ：为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。 要想对语言的性质进行研究，用这些定义来建立语言的数学模型是不够精确的。必须有更形式化的定义。 1.4.2 形式语言与自动机理论的产生与作用 * * 语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言的角度研究语言。1956年，他将语言L定义为一个字母表∑中的字母组成的一些串的集合： L?∑*。 字母表上按照一定的规则定义一个文法(grammar)，该文法所能产生的所有句子组成的集合就是该文法产生的语言。 1959年，乔姆斯基根据产生语言文法的特性，将语言划分成3大类。 1.4.2 形式语言与自动机理论的产生与作用 * * 1951年到1956年，克林(Kleene) 在研究神经细胞中，建立了识别语言的系统——有穷状态自动机。 1959年，乔姆斯基发现文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性，这一成果被认为是将形式语言置于了数学的光芒之下，使得形式语言真正诞生了。 1.4.2 形式语言与自动机理论的产生与作用 * * 20世纪50年代，巴科斯范式(Backus Nour Form 或 Backus Normal Form，BNF)实现了对高级语言ALGOL-60的成功描述。这一成功，使得形式语言在20世纪60年代得到了大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。 相应的理论用于其他方面。 1.4.2 形式语言与自动机理论的产生与作用 * * 形式语言与自动机理论在计算机科学与技术学科人才的计算思维的培养中占有极其重要的地位。 计算学科的主题：“什么能被有效地自动化”。