出版社:机械工业出版社
年代:2008
定价:29.0
本书以四类形式语言和四种自动机为主线,讨论了形式语言与自动机方面的主要理论成果和应用实例。
出版者的话
序言
前言
教学建议
第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具有e转移的有穷自动机
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
6.4.3标记语言
6.4.4XML和文档类型定义
习题
第7章下推自动机
7.1下推自动机的定义
7.2下推自动机接受的语言
7.3下推自动机和上下文无关文法的关系
7.4确定的下推自动机
习题
第8章上下文无关语言的性质
8.1上下文无关语言的泵引理
8.2上下文无关语言的封闭性
8.3上下文无关语言的判定算法
习题
第9章图灵机导引
9.1图灵机的基本模型
9.2图灵机的程序设计技术
9.2.1在状态中存储符号
9.2.2多道技术
9.2.3子程序技术
9.3图灵机的变形
9.3.1双向无限带
9.3.2多带
9.3.3非确定的图灵机
9.3.4双栈机
9.3.5作为枚举器的图灵机
9.4图灵机与计算机
9.4.1用计算机模拟图灵机
9.4.2用图灵机模拟计算机
9.4.3比较计算机与图灵机的运行时间
9.5图灵机与0型文法的关系
习题
第10章不可判定性
10.1递归集和递归可枚举集的性质
10.2通用图灵机和第一个不可判定问题
10.3归约方法和莱斯定理
10.4关于上下文无关语言的不可判定问题
*10.5波斯特对应问题的不可判定性及其应用
习题
第11章线性有界自动机和上下文有关文法
11.1线性有界自动机
11.2线性有界自动机和上下文有关文法的关系
11.3上下文有关语言的性质及其与递归集的关系
11.4各语言类之间的关系
习题
第12章确定的上下文无关语言和LR(k)文法
12.1确定的下推自动机的标准形式
12.2确定的上下文无关语言的性质
12.3LR(0)文法
12.4LR(0)文法与DPDA的关系
12.5LR(k)文法
习题
参考文献
书籍详细信息 | |||
书名 | 形式语言与自动机站内查询相似图书 | ||
丛书名 | 面向计算机科学与技术本科专业规范系列教材 | ||
9787111237761 如需购买下载《形式语言与自动机》pdf扫描版电子书或查询更多相关信息,请直接复制isbn,搜索即可全网搜索该ISBN | |||
出版地 | 北京 | 出版单位 | 机械工业出版社 |
版次 | 1版 | 印次 | 1 |
定价(元) | 29.0 | 语种 | 简体中文 |
尺寸 | 26 | 装帧 | 平装 |
页数 | 235 | 印数 | 5000 |
形式语言与自动机是机械工业出版社于2008.06出版的中图分类号为 TP301 的主题关于 形式语言-高等学校-教材 ,自动机理论-高等学校-教材 的书籍。