形式语言与自动机

　　本书扼要地介绍了形式语言与自动机的基本体系，是学习理论计算机科学基础的教材和参考书。书中主要介绍了形式语言的基本概念、自动机的模型以及形式语言与自动机的等价性，包括右线性文法与有限自动机、上下文无关文法与下推自动机、图灵机以及无限制文法等。同时介绍了自动机在通信领域的某些应用。本书不追求过多形式化讨论，强调基本概念的直观背景和主要定理证明的思路分析。书中配有较多的例题和习题，可作为工科计算机专业本科生的教材和研究人员的参考书。

暂缺《形式语言与自动机》作者简介

第1章  基础知识                  
 1. 1  集合与关系                  
 1. 2  逻辑                  
 1. 3  图                  
 1. 4  证明技术                  
 1, 4. 1  演绎证明                  
 1. 4. 2  反证法                  
 1. 4. 3  归纳定义与归纳法                  
 习题                  
                   
 第2章  语言及文法                  
 2. 1  语言的定义与运算                  
 2. 2  文法                  
 2. 3  文法的分类                  
 习题                  
                   
 第3章  有限自动机和右线性文法                  
 3. 1  有限自动机                  
 3. 1. 1  有限状态系统和有限自动机的概念                  
 3. 1. 2  有限自动机的形式定义                  
 3. 1. 3  设计有限自动机                  
 3. 2  不确定的有限自动机                  
 3. 3  DFA与NFA的等效                  
 3. 4  有c转换的不确定的有限自动机                  
 3. 5  正则集与正则式                  
 3. 6  右线性文法和正则集                  
 3. 7  正则表达式和有限自动机                  
 3. 8  右线性语言与有限自动机                  
 3. 9  右线性语言的性质                  
 3. 9. 1  确定的有限自动机的化简                  
 3. 9. 2  泵浦引理                  
 3. 9. 3  右线性语言的封闭性                  
 3. 9. 4  判定问题                  
 3. 10  双向和有输出的有限自动机                  
 3. 10. 1  双向有限自动机                  
 3. 10. 2  有输出的有限自动机                  
 习题                  
                   
 第4章  上下文无关文法与下推自动机                  
 4. 1  推导树与二义性                  
 4. 2  上下文无关文法的变换                  
 4. 3  Chomsky范式和Greibach范式                  
 4. 4  下推自动机                  
 4. 5  上下文无关文法与下推自动机                  
 4. 6  上下文无关语言的性质                  
 4. 6. 1  关于上下文无关语言的泵浦引理                  
 4. 6. 2  上下文无关语言的封闭性                  
 4. 6. 3  上下文无关语言的判定问题                  
 4. 6. 4  二义性                  
 4. 7  受限型上下文无关文法                  
 习题                  
                   
 第5章  图灵机                  
 5. 1  基本图灵机                  
 5. 2  图灵机的构造技术                  
 5. 2. 1  控制器的存储                  
 5. 2. 2  多道机                  
 5. 2. 3  核对符                  
 5. 2. 4  移位                  
 5. 2. 5  子程序                  
 5. 3  修改型图灵机                  
 5. 3. 1  双向无限带图灵机                  
 5. 3. 2  多带图灵机                  
 5. 3. 3  不确定的图灵机                  
 5. 3. 4  二维图灵机                  
 5. 4  图灵机与无限制文法                  
 5. 5  线性有界自动机与上下文有关文法                  
 习题                  
                   
 第6章  翻译                  
 6. 1  翻译式                  
 6. 2  转换器                  
 6. 2. 1有限转换器                  
 6. 2. 2下推转换器                  
 6. 3  词法分析                  
 6. 4  句法分析                  
 6. 4. 1  自上而下解析                  
 6. 4. 2  自下而上解析                  
 习题                  
                   
 第7章  自动机理论在通信领域的应用                  
 7. 1  状态机基本模型及其局限性                  
 7. 2  MSC和SDL简介                  
 7. 3  应用状态机模型描述协议                  
 附录  计算复杂性与可计算性基础                  
 参考文献