形式语言与自动机：第01讲-概论

1、形式语言与自动机Formal Languages and Automata Theory课程定位：揭示计算机科学与技术学科中计算的本质问题 什么能且如何被（有效地）自动计算。主要讨论计算机理论与应用中常用的各语言类对应的计算模型以及模型之间的联系与相互转换。形式语言与自动机课程目的： 培养计算机科学方面的理论素养，提高逻辑思维和解决相关问题的能力，为今后从事科学研究或技术开发打下扎实的基础。教材: 1、形式语言与自动机理论（第二版），蒋宗礼等，清华出版社，2007参考教材： 2、形式语言与自动机理论”，吴哲辉等编著，机械工业出版社，2008 “自动机理论、语言和计算导论”，孙家啸等译，机械工业

2、出版社形式语言与自动机前续课程： 离散数学 数理逻辑、集合论等MOOC素材: 1、自动机(Automate），斯坦福大学CS154 /course/418/Automata/ 形式语言与自动机形式文法与自动机理论的发展概况学习意义与课程特点课程教学内容与前期准备符号语言第一章 课程概述及预备知识形式语言与自动机理论的发展概况何为形式语言形式语言的研究概况计算模型相关研究领域何为“语言”：斯大林 语言是人们所理解的字和组合这些字的方法。韦波斯特 语言是为大范围人群懂得、并能使用的字符以及组合这些字符的方法的一个统一体。形式语言语言：自然语言（ 英语、汉语）、 符号语言（ 程序设计语言、标记语言、

3、算法 等）形式语言 元语言：用数学方法将符号语言抽象成一个数学系统，对其进行严格的形式化定义，并构建适当的描述模型，发展相关的知识和理论，使之在科学实践中具有良好的指导作用。形式语言形式语言与自动机理论的发展概况何为形式语言形式语言的研究概况计算模型相关研究领域 数理语言学家致力于用数学方法研究自然语言的结构，试图用计算机模拟。研究概况 1956年，宾夕法尼亚大学的语言学家 N. Chomsky 第一次提出用形式语言研究自然语言的方法。N. Chomsky 关于用形式文法派生语言的思路： 一组有限多个符号构成的集合 ，称为字母表 ； 中所有符号串构成集合 *， * 每一个子集可视为上的一个语言

4、 L； 一个语言 L（所有句子） 可以按照文法 G L 的一系列描述规则（算法）形式化地派生出来。并给出了文法的乔姆斯基（Chomsky）体系。研究概况0 型文法（短语结构文法或无限制文法）1 型文法（上下文有关文法）2 型文法（上下文无关文法） 3 型文法（正则文法）派生符号语言的乔姆斯基（Chomsky）文法体系：研究概况研究概况 1936年，英国数学家阿兰.图灵（A. M. Turing, 1912-1954）提出一种抽象计算模型 图灵机( TM )，能根据内部状态，在一个无限长磁带上进行读、写、移动等简单操作，计算所有可计算的函数；是模拟计算机算法的计算逻辑和研究可计算性的形式化描述工

5、具。 TM 的两个基本性质: 计算对象能用有穷方式描述; 计算过程必须由一系列离散的、可以机械执行的步骤组成。识别符号语言的 A. Turing自动机体系：基本的图灵机模型的物理装置：控制器：左右移动、读字符、修改方格字符、改变控制器状态 ； 模拟计算机的基本操作。装置改进：单带多道；子程序功能；单带无穷；多带；多维；通用 TM。研究概况研究概况1943年，McCulloch-Pitts神经模型：莫克罗（WSMcCulloch）和彼特（WPitts）1951- 1956年，数学家克林（Kleene）：研究神经细胞时，基于图灵机建立了确定有穷状态自动机 DFA，用其识别语言； 并证明DFA与RE

6、的等价性。 1957年，米凯尔.拉宾 & 达纳.斯科特（Dana Stewart Scott，1976年图灵奖）将确定状态自动机 DFA 扩展为非确定有穷状态自动机 NFA，从而简化了机器的描述建模过程，提高了解题（识别语言）速度，为其在机器翻译、文献检索的语言识别及符号处理等中的应用奠定了基础。识别符号语言的 A. Turing 自动机体系：问题：给定的形式文法和自动机描述的是否是同一符号语言；两种形式化方法是否等价；如何证明？二者能否在等价基础上相互模拟与转换？如何证明这种转换的正确性？如何实现转换的形式化和自动化，即，是否能用计算机的算法实现？ 1959年，N.乔姆斯基发现：文法和自动机

7、分别从派生和识别角度表达语言，并证明文法和自动机的等价性，开启了用数学方法研究形式语言的先河。研究概况0 型文法（无限制文法） 图灵机 1 型文法（上下文有关文法） 线性有界自动机 2 型文法（上下文无关文法） 下推自动机 3 型文法（正则文法） 有穷状态自动机 两种计算模型的对应关系：研究概况1977 Amir Pnueli.将自动机与逻辑建立关系，基于此发展了模型检测技术 * 判定性、复杂性、表达能力研究概况形式语言与自动机理论的发展概况何为形式语言形式语言的研究概况计算模型相关研究领域计算模型相关研究领域1、可计算性问题的提出：希尔伯特（D. Hilbert, 1862-1943）纲领

8、是否对各个数学分支都能建立一套形式化的公理系统，使得所涉及领域内的任何命题，都可通过系统的有限步推导，判断命题是否正确。2、存在不可判定命题：歌德尔（K. Godel, 1906-1978） 在包含初等数论的协调的形式系统中，存在不可判定问题；即，存在一个命题 A，无法在该系统内证明 A 或 A 为真。3、可计算问题转换为： 是否存在这样一种抽象的形式系统，它可以衡量什么问题是可以判定（可计算）的，什么问题是不可判定（不可计算）的。若干可计算模型：1、英国数学家图灵 1936 年提出图灵机 2、赫尔布拉德(1932)、哥德尔（1936）、克林尼（1936）提出一般递归函数 3、邱奇（1933-

9、1935 ）提出 - 演算 成果：1、邱奇证明：一般递归函数 同 - 可定义的等价性；2、克林尼证明：图灵可计算 同 - 可定义的等价性；邱奇 - 图灵论题：一个函数是可计算的当且仅当它是图灵机可计算的（或 - 可定义的）。计算模型的相关研究领域形式文法与自动机理论的发展概况学习意义与课程特点课程教学内容与前期准备符号语言第一章 课程概述及预备知识一、深化计算机基础理论学习： 1、形式语言为计算机程序语言编译过程提供了理论基础； 3、有限状态自动机为数字逻辑电路等设计提供了描述手段； 2、图灵机模型为计算机的计算理论提供了模型基础。学习意义与课程特点三、人才培养： 形式语言与自动机理论对于计算

10、机领域人才的计算思维能力的培养起到至关重要的作用。二、应用拓展： 1、在人工智能的自然语言理解与翻译、WEB服务标注语言词法及语法结构与模式识别等方面有着广泛的应用。 2、为操作系统的状态变换，网络状态描述等各种模型系统的建模提供方法。学习意义与课程特点“计算思维能力”梯级式训练过程：学习意义与课程特点本课程强调：1、抽象性：形式语言研究如何利用数学方法抽象出符号语言的结构特征及相关的文法规则；自动机理论研究各种能自动处理符号串的计算模型；二者描述的理论基础是离散数学，内容具有一定抽象性。2、构造性：课程包含大量的构造性内容，如给定语言构造生成语言的形式文法或识别语言的自动机；给定文法构造等价

11、的自动机等3、理论性：形式语言与自动机理论的大部分内容属于理论形态，拥有完整的理论体系；包含许多定义、定理及其相关的递归证明。学习意义与课程特点形式文法与自动机理论的发展概况学习意义与课程特点课程教学内容与前期准备符号语言第一章 课程概述及预备知识第四章 正则表达式以及其与文法、自动机的等价性第三章 各种有限状态自动机及其相互等价性第五章 正则语言的性质第六章 上下文无关文法第二章 形式文法28第一章 课程概述及预备知识课程教学内容第七章 下推自动机以及其与上下文无关文法的等价性第八章 图灵机初步第九章 案例分析（语言验证、自然语言理解、状态跟踪等）课程前期准备 集合与归纳证明集合的表示： 列

12、举法、命题法集合的基数（势）：有穷集合、可数无穷集合、不可数无穷集合集合关系的定义： A B 、 A = B、 集合的运算： A B、A B、A B、A B、 A、(A ) = 2A、二元关系： 有序偶集合关系的性质： 自反性、反自反性、对称性、反对称性、传递性等价关系： 具有自反、对称、传递性质的关系等价划分与等价类： 用等价关系R对集合 S 进行的划分, 每个子集 Si 为一个等价类关系的合成与闭包： 正闭包，记为 “ R+ ” - 满足 “传递” 性质； 克林闭包，记为 “ R* ” - 满足 “自反、传递” 性质递归定义： 构造无穷集合； 归纳证明： 证明无穷集合元素均具有 P 性质形

13、式语言与自动机理论的发展概况学习意义课程特点课程教学内容与前期准备符号语言第一章 课程概述及预备知识定义 1.1 字母表是一个非空有限集合，通常记作，其中元素称为字母表的字符。字母表及其字符特点： 1、字母表具有非空、有穷性； 2、字符具有不可分性、整体性； 3、字符具有可区分性 、可辨认性。字母表与字符串例：考察以下字母表： 1 = aa, ab, bb ； 2 = a, a, b, b ； 3 = a, b, a 。字母表与字符串定义 1.2 设1，2 是两个字母表，1，2 的乘积定义为12 = ab | a 1 b 2 。例： 1、 0, 1 a, b, c = 0a, 0b, 0c,

14、1a, 1b, 1c ; 2、 a, b, c 0, 1 = a0, a1, b0, b1, 0c, c1 ; 3、 aa, ab, bb 0, 1 = aa0, aa1, ab0, ab1, bb0, bb1 字母表与字符串定义 1.3 设是一个字母表，的 n 次幂可递归定义为： 0 = ; n = n-1, n1， 其中，表示 由 0 个字符（空字符）组成。辨异 - 与 空集 的区别。定义 1.4 设是一个字母表， 的正闭包： + = 2 3 . , 的克林闭包： * = 0 2 3 . , 是 上全体字符串构成的集合字母表与字符串例：1、 0, 1 + = 0, 1, 00, 01, 1

15、0, 11, 000, 001, 010, 011, 100, . ; 2、 0, 1 * = , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 3、 a, b, c * = , a, b, c, aa, ab, ac, ba, bb, bc, , aaa, 字母表与字符串定义 1.5 设是一个字母表， x *， x 叫做 上的一个句子（字符串、符号串）。例： 1、 0, 1 * = , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . ; 2、 a, b, c * = , a, b, c,

16、 aa, ab, ac, ba, bb, bc, , aaa, 3、 an = aaa 表示 n 个 a 组成的字符串。 例： | ab | = 2 , | aab | = 3, | an | = n , | a0 | = | = 0定义 1.6： 设是一个字母表， x *，字符串 x 中字符出现的总个数叫做该串的长度，记作 | x |。字母表与字符串定义 1.7： 设 和 是任意两个字符串，则 = 当且仅当 | | = | |，并且组成 的字符与组成 的字符依次对应相同。 例： 若 = ab， = ab， 则 = ； 若 = ab， = ba， 则 。 字母表与字符串定义 1.8 ： 1、设

17、 和 是 * 上任意的两个字符串， 和 的连接构成一个新句子，记作 （简记为 ），该句子由串 后直接接串 组成。字母表与字符串 2、对于 n 0，字符串 的 n 次幂为： （1） 0 = ；（2） n = n-1 例：设 = 0, 1 , x = 001, y = 1101； 1、 x0 = y0 =; 2、 xy = 0011101; 3、x2 = 001001 4、 y4 = 1101110111011101,字符串连接性质：对于* 上任意字符串 x, y, z, 连接运算具有以下性质： 1、结合律： ( xy ) z = x ( yz )。 2、左消去律： xy = xz y = z 。

18、 3、右消去律： yx = zx y = z 。 4、唯一性： 存在唯一确定的 a1, a2, , an , 使得 x = a1a2 an。 5、单位元素： = = 字母表与字符串 设 是一个字母表，任意字符串 x , y, z * ，且 x = yz， 则称 y 是字符串 x 的前缀，z 是 x 的后缀；如果 z ，则称 y 是 x 的真前缀；如果 y ，则称 z 是 x 的真后缀。定义 1.9： 字母表与字符串例： 求 = a, b 上字符串 abaabb 的前缀、后缀、真前缀、真后缀？前缀： , a, ab, aba, abaa, abaab, abaabb真前缀： , a, ab, a

19、ba, abaa, abaab后缀： , b, bb, abb, aabb, baabb, abaabb真后缀： , b, bb, abb, aabb, baabb是每个字符串的前缀、后缀、子串。定义1.10： 设= a1 a2 an 是任意字符串，称字符串 an a2 a1是的逆，记作T 若 = T，则称为回文。字母表与字符串例：设 = abcd， T = dcba例：字符串 0110110 和 deed 都是回文。定义 1.11： 设是任意字母表， L *， L 称为字母表上的一个语言；x L， x 叫做 L 的一个句子。符号语言及其运算性质例：设 = 0, 1 , 可定义 上的不同语言如

20、下： 1、 0, 1 ; 00, 11 ; 0, 1, 00, 11, 01, 10 ; 2、 0, 1 *; 00, 11 *; 0, 1, 00, 11, 01, 10 *; 定义 1.12 ：设 1 和 2 是字母表， L1 1*， L2 2*，L1 和 L2 的乘积 L1 L2= xy | x L1 y L2 是字母表 1 2 上的一个语言。例: 设 L1 = ab，ac , L2 = e，bc , 有 L1L2 = abe，abbc， ace，acbc 。符号语言及其运算性质例：设 = 0, 1 , 分析下列语言的结构特征及其关系。1、有穷语言 ？无穷语言 ?2、L5L7 = L6

21、？ L5L7 = L8 ？ L9 = L10 ？3、 L6 L5L7 ？ L9 L10 ？ L6 L11？符号语言及其运算性质定理 1.1 ：设 A、B、C、D 是 上任意语言，有 1）A = A = 2）A = A = A 3）（AB）C = A（BC）4）若 A B 和 C D，有 AC BD5）A（B C）= AB AC符号语言及其运算性质 - 摘自离散数学书版本1P1456）（B C） A = B A C A7） A（B C） A B A C8）（B C）A B A C A9） Am An = Am+n10）（ Am ）n = Amn 11）若 A B，则 An Bn 符号语言及其运算性质 12）A* = A+ 13）An A*， 其中，n 0 14） An A+， 其中，n 1 15） A A B 16） A B A 17）若 A B，则 A B符号语言及其运算性质18）若 A B，则 A+ B+19） AA* = A*A =