形式语言与自动机(第2版)

图书标准信息

• 作者 杨娟；石川；王柏
• 出版社 北京邮电大学出版社有限公司
• 出版时间 2017-03
• 版次 1
• ISBN 9787563549979
• 定价 29.00元
• 装帧 其他
• 开本 大16开
• 纸张 胶版纸
• 页数 210页
• 字数 339千字

【内容简介】

·

【目录】

章基础知识
1.1集合与关系
1.2逻辑
1.3图
1.4证明技术
1.4.1演绎证明
1.4.2反证法
1.4.3归纳定义与归纳法
1.5典型例题解析
题
第2章语言及文法
2.1语言的定义与运算
2.2文法
2.3文法的分类
2.4典型例题解析
题
第3章有限自动机和右线文法
3.1有限自动机
3.1.1有限系统和有限自动机的概念
3.1.2有限自动机的形式定义
3.1.3设计有限自动机
3.2不确定的有限自动机
3.3dfa与nfa的等效
3.4有ε转换的不确定的有限自动机
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有输出的有限自动机
3.11正则表达式和有限自动机的应用
3.11.1unix中的正则表达式
3.11.2文本编辑程序
3.11.3词法分析
3.11.4文本搜索与字符串匹配.
3.11.5单词拼写检查
3.12典型例题解析
题
第4章上下文无关文法与下推自动机
4.1推导树与二义
4.2上下文无关文法的变换
4.3chomsky范式和greibach范式
4.4下推自动机
4.5上下文无关文法与下推自动机
4.6上下文无关语言的质
4.6.1上下文无关语言的泵浦引理
4.6.2上下文无关语言的封闭
4.6.3上下文无关语言的判定问题
4.6.4上下文无关语言的二义
4.7受限型上下文无关文法
4.8上下文无关文法的应用
4.8.1上下文无关文法在语法分析中的应用
4.8.2上下文无关文法变换的应用
4.8.3上下文无关文法的其他应用
4.9典型例题解析
题
第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线有界自动机与上下文有关文法
5.6典型例题解析
题
第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.2msc和sdl简介
7.3应用机模型描述协议
附录计算复杂与可计算基础
参文献