形式语言与自动机
版权信息书 名: 形式语言与自动机
作者：陈有祺
出版社：机械工业出版社
出版时间： 2008
ISBN: 9787111237761
开本： 16
定价: 29.00 元
内容简介本书以四类形式语言（短语结构语言、上下文有关语言、上下文无关语言、正则语言）和四种自动机（有穷自动机、下推自动机、图灵机、线性有界自动机）为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。书中每一章的最后都配有大量不同难度的习题，有助于读者掌握本书内容。
本书采用通俗的语言和形象化的方法来表达概念和定理，逻辑严谨、思维缜密，可作为高等院校计算机及相关专业“形式语言与自动机”课程的教材。
作者简介陈有祺，南开大学信息技术科学学院教授，多年来一直从事计算机软件方面的教学和研究工作，从1993年起享受国务院政府特殊津贴。讲授的课程主要有程序设计语言．编译原理，数据结构、形式语言与自动机等，研究领域包括编译理论、人工智能、自然语言理解，形式语言等。1980年至1982年在美国西密歇根大学作访问学者，研修人工智能和形式语言，回国后一直为研究生讲授“形式语言与自动机”课程。相关著作包括：《BCLR（k）文法及其分析算法》、《广义上下文无关文法和它的语法分析》、《从输入输出序列确定自动机的结构》，《形式语言与自动机》等。
编辑推荐本书以四类形式语言（短语结构语言，上下文有关语言。上下文无关语言。正则语言）和四种自动机（有穷自动机、下推自动机．图灵机，线性有界自动机）为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。
本书的主要特色：
取材丰富。涵盖了该领域国内外现有教材的主要内容。
在写作方法上，循序渐进，深入浅出。在概念的引入和定理的证明上，尽量采用通俗的语言和形象化的方法来表达。
理论与实际相结合。除具有配合定理和定义的大量例题外，许多章节还有现代计算机技术中应用的实例。
适应面广。既适合作为本科生的教材，也适合作为研究生的教材。
目录出版者的话
序言
前言
教学建议
第1章预备知识
1.1定理及其证明方法
1.1.1演绎法
1.1.2反证法
1.1.3归纳法
1.2集合及其基本运算
1.2.1集合基础知识
1.2.2集合的基本运算
1.2.3关系与映射
1.3图和树简介
1.3.1图的基本概念
1.3.2图的矩阵表示
1.3.3树的基本知识
1.4字母表、字符串和语言
习题
第2章文法的一般理论
2.1问题的提出
2.2形式文法与形式语言
2.3文法的乔姆斯基分类
习题
第3章有穷自动机
3.1非形式化描述
3.2有穷自动机的基本定义
3.3非确定的有穷自动机
3.4具有￡转移的有穷自动机
3.5有穷自动机的应用
3.5.1在文本中查找字符串
3.5.2用于文本搜索的非确定的有穷自动机
3.5.3识别关键字集合的DFA
3.6具有输出的有穷自动机
习题
第4章正则表达式
4.1正则表达式的定义
4.2正则表达式和有穷自动机的关系
4.3则表达式的等价变换
4.3.1交换律与结合律
4.3.2单位元与零元
4.3.3分配律
4.3.4与“*”构造有关的定律
4.3.5发现正则表达式定律的一般方法
4.4正则表达式的应用
4.4.1UNIX中的正则表达式
4.4.2词法分析
4.4.3查找文本中的模式
习题
第5章正则语言的性质
5.1正则文法和有穷自动机的关系
5.2正则语言的泵引理
5.3正则语言的封闭性
5.4正则语言的判定算法
5.5有穷自动机的最小化
习题
第6章上下文无关文法
6.1上下文无关文法的语法分析
6.2上下文无关文法的化简
6.3上下文无关文法的范式
6.4上下文无关文法的应用
6.4.1用上下文无关文法描述语言
6.4.2语法分析器生成工具YACC
……
第7章下推自动机
第8章上下文无关语言的性质
第9章图灵机导引
第10章不可判定性
第11章线性有界自动机和上下文有关文法
第12章确定的上下文无关语言和LR（k）文法
参考文献
……