计算理论---正则语言全.ppt

《计算理论---正则语言全.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算理论导引2021/10/61本课程关注计算理论的三个传统的核心领域：自动机理论可计算性理论复杂性理论计算理论导引2021/10/62主要问题：计算机的基本能力和局限性是什么？随着计算机能力的越来越强大，这个问题的理论指导意义越来越大计算理论导引2021/10/63核心问题：是什么使得某些问题很难计算，而又使另外一些问题容易计算？复杂性理论寻求以某种方式量度计算问题的难与易，并寻求其中的原因以及优化方法。计算复杂性理论2021/10/64一个重要成果：发现了一个按照计算难度给问题分类的完美体系计算复杂性理论2021/10/65应对难计算问题方法：通过弄清问题难计算的

2、原因，或可以改变问题提法。转而求近似解寻求满意解选择计算类型计算复杂性理论2021/10/66典型应用之一：密码问题。计算复杂性理论2021/10/67问题发现：并不是所有数学问题都可以利用计算机可以解决的，存在一些基本数学问题是不能用计算机解决的。可计算性理论2021/10/68可计算性理论和复杂性理论是密切相关的：在可计算性理论中把计算问题分成算法可解的和算法不可解的两类在复杂性理论中，把问题分成容易计算的和难以计算的两类可计算性理论2021/10/69自动机理论阐述了计算的数学模型的定义和性质，为计算机提供了一个准确的形式化的定义在计算机科学的若干应用领域中起着

3、作用，是学习计算理论的非常好的起点自动机理论2021/10/610两个模型：有穷自动机模型用于文本处理、编译程序以及硬件设计等；上下文无关模型用于程序设计语言和人工智能自动机理论2021/10/611第一部分自动机与语言第1章正则语言研究内容有穷自动机非确定性正则表达式非正则语言2021/10/612下面是一系列需要用到的基本的数学对象、工具和概念，例如：集合、序列、多元组函数、关系、图字符串与语言、布尔逻辑；相关术语，例如：定义、命题、定理、证明（包括构造性证明、反证法、归纳法）相关的数学概念和术语2021/10/613字母表：由字符串组成的一个非空有限集称为一个字

4、母表，记为串：是指某个字母表上的字符组成的有限序列串长，空串ε，逆串xR串的连接，前缀，后缀，子串，真子串通常用*表示上的全体串（包括空串）的集合，而+表示上的全体非空串的集合*上连接运算°封闭并满足结合律，但不满足交换律（*，°）构成一个单元半群字母表和串2021/10/614字母表上满足一定条件的串的集合L称为上的一个语言举例：L1={x∈{0,1}*

5、x=0或者x的首位为1}L2={x∈{0,1}*

6、

7、x

8、≤3}L3={anbn

9、n≥1}L3={x∈{a,b}*

10、x=xR}性质：设L是字母表上的一个语言，记L0={ε}，Ln=Ln-1°L，L

11、*=∪i=0，，∞L，L+=∪i=1，，∞L，则L+=L*°L=L°L*，L*=L+°{ε}语言2021/10/615Chomsky提出可以在一个字母表上给出一组产生规则，根据这些规则推导出来的全体句子组成的集合就构成一个语言，这样的一组规则就称为文法文法是一个四元组G=（V，T，P，S），其中V是变量的一个有限集合，T是终极符的一个有限集（或称为字母表），V∩T=ø；S是初始符号（S∈V）；P是产生式规则，P中的元素为（α，β），表示为α→β，α，β∈（V∪T）*，而且α中至少有一个字符来自V中从文法G产生语言L（G）的过程：从初始符开始，根据P中的一个产生式可

12、以进行一步推导，如果通过若干步推导得到一个只由终极符组成的串，这个串就是L（G）中的一个句子。所有能通过推导得到的句子集合就是语言L（G）文法2021/10/616设G=（V，T，P，S）是一个文法，则S是G中的一个句型若δαγ是G中的一个句型，α→β是G中的一个产生式，则δβγ也是G中的一个句型，从δαγ中得到δβγ的过程称为推导不含非终极符的句型是L（G）的一个句子文法2021/10/617文法举例G1=(V1,T1,P1,S)，其中V1={S,A}，T1={0,1}，P1:S→0S;S→OA;S→1A;A→ε则L(G1)={0i1j

13、i,j≥0}G2=(V2,T

14、2,P2,S)，其中V2={S,A,B}，T2={a,b}，P1:S→aB;S→bA;A→bAA:A→a;A→aS;B→b;B→bS;B→aBB则L(G2)={w∈{a,b}*

15、w中a的个数等于b的个数}文法2021/10/618语言识别器语言识别器又称为自动机，它有三个部分：有限状态控制器、输入带和辅助存储器。有限状态控制器通过读写头或只读输入头与其它两部分连接自动机识别语言的过程：一个自动机所接受的所有字符串的集合就是该自动机所确定的一个语言ana2a1有限状态控制器辅助存储器2021/10/619有穷自动机有穷自动机是描述能力和资源极其有限的