形式语言与自动机

《形式语言与自动机》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、形式语言与自动机理论为什么学？学什么？怎么学？计算机科学与技术专业人员的4种基本专业能力：（1）计算思维能力；（2）算法的设计与分析能力；（3）程序设计和实现能力；（4）计算机软硬件系统的认知、分析、设计与应用能力。引言培养学生的形式化描述和抽象思维能力，了解和掌握“问题——形式化描述——自动化（计算机化）”的解题思路。“什么能被有效自动化”————计算学科之主题计算机科学与技术专业人员的4种基本专业能力：（1）计算思维能力；（2）算法的设计与分析能力；（3）程序设计和实现能力；（4）计算机软硬件系统的认知、分析、设计与应用能力

2、。引言一、课程性质FormalLanguagesandAutomataTheoryTheFundamentalofComputingTheoryIntroductiontotheTheoryofComputation二、课程特点：抽象和形式化；既有严格的理论证明；又有很强的构造性；包含一些基本模型的建立、性质等。三、课程主要内容1、语言理论2、自动机理论3、可计算性基本理论本课程内容属于计算机科学的基本理论自然语言：人与人之间交流的基本手段。如：汉语、英语、俄语、法语、…等人工语言：主要用于人与计算机之间的交流。如：程序设计语言（也有例外，如世

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.——U

4、RG语言的运算及性质证明。可计算性基本理论：判定问题与不可判定性形式语言（FormalLanguage）课程特点：抽象和形式化；既有严格的理论证明；又有很强的构造性；包含一些基本模型的建立、性质等。四、教材与教学参考书教材：吴哲辉《形式语言与自动机理论》，北京，机械工业出版社，2007年4月，¥20。主要参考书：１．J.Hopcroft,J.D.Ullman,《IntroductiontoAutomataTheory,LanguageandComputation》California,Addison-WesleyPublishingCompan

5、y,1979.（2002年清华，影印版）2．刘田译，自动机理论、语言和计算导论，机械工业出版社，2005，¥39。3．蒋宗礼，形式语言与自动机理论，清华大学出版社，2003，¥28。（另带习题解答）另外的预备知识1、关于集合及运算（并、交、差、有限集、无限集、幂集、笛卡尔乘积等）2、关于二元关系（三歧性、等价关系、等价类等）3、关于常用证明方法（演绎推导、反证、例证、数学归纳、构造证明等）4、树和图的应用第1章语言及其表示语言—某个字母表上满足某些特定条件的字符串的集合1.1字母表、串和语言字母表（Alphabet）：由字符组成的非空有限集，通常

6、用∑表示。空集不能作为字母表无限集也不能作为字母表自然语言人工语言—例如：英语的字母表∑={a,b,…,y,z,A,B,…Y,Z,，,。,“，”,；}∑={0,1}也可以看作一个字母表，一个二进制数可看作这个字母表上的一个字符串。串（String）：由某字符表上的字符组成的有限序列。例如：0100101是字母表∑={0,1}上的一个串。串的长度：一个串中字符的个数。设x为字母表∑上的一个串，x的长度记为

7、x

8、。例如

9、0100101

10、=7空串：不含任何字符的串，即长度为零的串，记为。前缀、后缀、子串串的逆：把一个串中的字符逆向顺序重新排列得到的另一

11、个串设x为一个串，x的逆记为xR例：若x=0100101则xR=1010010易知1）

12、xR

13、=

14、x

15、2）空串的逆仍是空串：εR=ε串的连接（concatenation）运算串的幂运算串的连接运算又称为串的乘法运算。类似于从数的乘法运算推广到数的幂运算那样，也可以从串的乘法推广到串的幂运算。设x为一个串，则定义代数系统　间的同构关系语言（Language）语言几种基本运算对语言的理解句型、推导与句子文法所产生的语言举例举例1.3语言识别器语言识别器同文法一样，都是对（可能为无限集的）语言提供有限表示的一种方式。语言识别器也称为自动机。如果说文法是

16、从产生语言的角度来表示语言，那么自动机是从识别语言的角度来表示语言。自动机的结构可以大致表示成下图的形式。辅助存储器a1a2an…有限状