形式语言与自动机.pptVIP

形式语言与自动

机理论

为什么学？

学什么？

怎么学？

引言

计算机科学与技术专业人员的4种基本专业能力：

（1）计算思维能力；

（2）算法的设计与分析能力；

（3）程序设计和实现能力；

（4）计算机软硬件系统的认知、分析、设计与应用能力。

引言

计算机科学与技术专业人员的4种基本专业能力：

（1）计算思维能力；

（2）算法的设计与分析能力；

（3）程序设计和实现能力；

（4）计算机软硬件系统的认知、分析、设计与应用能力。

培养学生的形式化描述和抽象思维能力，了解和掌握

“问题——形式化描述——自动化（计算机化）”

的解题思路。

“什么能被有效自动化”————计算学科之主题

一、课程性质

FormalLanguagesandAutomataTheory

TheFundamentalofComputingTheory

IntroductiontotheTheoryofComputation

二、课程特点：

抽象和形式化；

既有严格的理论证明；

又有很强的构造性；

包含一些基本模型的建立、性质等。

三、课程主要内容

1、语言理论

2、自动机理论

3、可计算性基本理论

本课程内容属于计算机科学的基本理论

语言理论：

自然语言

语言

人工语言

自然语言：人与人之间交流的基本手段。

如：汉语、英语、俄语、法语、…等

人工语言：主要用于人与计算机之间的交流。

如：程序设计语言

（也有例外，如世界语）

形式语言：研究自然语言和人工语言都必须遵循的一般规律

研究字符串集合及其性质的学科

计算机处理的主要对象

Chomsky文法体系：4种类型的文法及其产生的语言

正规文法RG——正规语言RL；

上下文无关文法CFG——上下文无关语言CFL；

上下文有关文法CSG——上下文有关语言CSL；

无限制文法URG——递归可枚举语言r.e.。

自动机理论：

语言（形式语言）识别器

4种类型自动机与4类文法相对应

有限自动机FA——RL——RG

下推自动机PDA——CFL——CFG

线性界限自动机LBA——CSL——CSG

图灵机TM——r.e.——URG

语言的运算及性质证明。

可计算性基本理论：

判定问题与不可判定性

Ø形式语言（FormalLanguage）

“为广大人群所理解的字和组合这些字的方法”——语言学家

字符语法（文法）

语言————语言的数学模型（形式语言）

抽象：以便于对语言的结构、性质、生成、识别进行研究。

形式语言与自动机理论的产生与作用：

1956，Chomsky从产生语言的角度抽象地将语言形式地定义为由

一个字母表中地字母组成的一些串的集合，组成句子的规则为文法；

1951－1956，Kleene从语言识别角度，给出语言的另一种描述——

自动机，其所识别的句子组成语言；1959，Chomsky证明文法与自

动机的等价性，此时形式语言诞生。

用于描述程序设计语言文法；模型化处理；计算思维培养等。

课程特点：

抽象和形式化；

既有严格的理论证明；

又有很强的构造性；

包含一些基本模型的建立、性质等。

四、教材与教学参考书

教材：吴哲辉《形式语言与自动机理论》，北京，机械工业出

版社，2007年4月，¥20。

主要参考书：

１．J.Hopcroft,J.D.Ullman,《IntroductiontoAutomataTheory,

LanguageandComputation》California,Addison-WesleyPublishing

Company,1979.（2002年清华，影印版）

2．刘田译，自动机理论、语言和计算