有限自动机理论CH.ppt

有向回路当v0=vk时称为一条(有向)回路。v1v2v3v4v5定义1-13树01设G=(V,E)为一个有向图。02当G满足如下条件时，称G为一棵(有向)树：?v?V，v没有前导，且v到树中的其他顶点都有一条有向路，该顶点称为树G的根；01每个非根顶点有且仅有一个前导；02每个顶点的后继按其拓扑关系从左到右排序。031.5语言任意字符的集合是一个字母表。如26个英文字母表；10个阿拉伯数字字母表；24个希腊字母表；二进制字母表0102字母表有非空性、有穷性、单一性一般使用∑表示字母表。字母表中的字母按照某种顺序排列成的字符的序列语言研究的三个方面01如何给出一个语言的表示。02对于有穷语言，使用列举法；03对于无穷语言，需要考虑语言的有穷描述。语言研究的三个方面（续）1对于一个给定的无穷语言是否存在有穷描述（有穷表示）。2注意：并不是所有的无穷语言都存在有穷表示。具有有穷表示的语言的结构以及结构的描述问题。1.6常用术语用?代表空串，{?}代表仅含有空串的集合。01.用?代表空集，表示一个元素都不包含的集合。02.用?代表字母表。03.常用术语（续）040301用??代表两个字符串?与?的连接（并置）则??=a1a2a3…anb1b2b3…bm。若?=a1a2a3…an,?=b1b2b3…bm;特别：??=??=?02用代表?n的n次连接?0=??n=?n-1?，n0A={a1,a2,a3,…,an}01B={b1,b2,b3,…,bm}02用AB代表集合A与B的连接AB={a1b1，a1b2，a1b3，…，a1bm，a2b1，a2b2，a2b3，…，a2bm，a3b1，a3b2，a3b3，…，a3bm，…anb1，anb2，anb3，…，anbm}AФ=ФA=Ф一般，AB与BA是不相等的。AB与BA在什么情况下相等?当A=B；A或B中有一个为{ε},则A{ε}={ε}A=AA和B中有一个为Ф，则AФ=ФA=ФAn代表集合A的n次连接(幂)01A的n次幂定义为：A0={?}An=An-1An?102A*代表A上所有字符串的集合即表示集合A中的所有字符串进行任意次连接而形成的串的集合A*称为集合A的闭包(克林闭包)01.A*=A0∪A1∪A2∪…∪An02.1.3.2归纳法归纳法是从特殊到一般的逻辑推理方法。分为完全归纳法和不完全归纳法两种形式。完全归纳法是根据一切情况的分析而作出的推理。01由于必须考虑所有的情况，得出的结论是完全可靠的。02归纳法（续）01不完全归纳法是根据一部分情况作出的推理。02不能作为严格的证明方法。在自动机理论中，普遍使用数学归纳法证明某个命题。数学归纳法可以使用01“有限步骤”解决“无限”问题。02对于一切非负整数n的命题M(n)M(0)为真；假设对于任意的k?0，M(k)为真，能够证明M(k+1)为真则对一切n?0，M(n)为真。213第(1)步称为归纳基础第(2)步称为归纳步骤第(2)步中“设对于任意的k?0，M(k)为真”，称为归纳假设数学归纳法的简化假设结论对于n成立，证明结论对于n＋１成立。02对于0，证明结论成立；011.3.3集合递归定义与归纳证明基础22%极小性限定(有限性)40%归纳38%递归定义递归定义集合步骤首先定义该集合中最基本的元素x1,x2,x3,…xm02基础：01x1,x2,x3,…xn对于该集合中的元素使用某种组合方法对这些元素进行处理后所得的新元素在该集合中归纳：有限性：只有满足(1)和(2)的元素才在集合中递归定义集合的优点除集合的基本元素(直接定义)外集合中的元素的产生遵从相同的规律。例1-6Fibonacci数01Fibonacci数组成的集合为：{0,1,1,2,3,5,8,13,21,34,55,…}02基础：0和1是最基本的两个元素；归纳：若m是第i个元素,n是第i+1个元素则第i+2个元素为n+m;只有满足(1)和(2)的数，才是集合的元素010302例括号匹配的串构成的集合的定义{(),()(),(()),…}基础：()是最基本的串若S是括号匹配的串,则(S)是括号匹配的串01若S是括号匹配的串,则SS是括号匹配的串0