未读消息消息

购物车

我的订单

个人中心

店铺

我的订单收藏商品

拍卖

拍卖交易我的竞拍收藏拍品

我的好友资金账户

卖家中心

客服 |

帮助中心 9:00-20:30 在线留言

客服电话

010-89648155

服务时间

客服咨询 08:00-21:00

纠纷处理

09:00-12:30

13:30-18:00

图书审核 09:00-18:00

监督与建议

请选择

手机孔网

形式语言与自动机导论

作者: 林兹著

出版社: 机械工业出版社

出版时间: 2005-09

版次: 1

ISBN: 9787111167884

定价: 36.00

装帧: 平装

开本: 16开

纸张: 胶版纸

页数: 289页

原版书名: An Introduction to Formal Languages and Automata

丛书: 计算机科学丛书

分类: 计算机与互联网

53人买过

　　主要介绍形式语言、自动机、可计算性和相关内容。本书特别注意定义、定理的准确性和严格性，在定理的证明中给出了直观的动机和框架，避免多余的数学细节，这有利于培养学生形式化和严格的数学推理能力，加强对问题的理解；本书通过精心设计的大量示例，生动剖析了各种定理和定义，概念清晰，深入浅出。每章后面还给出了难度不同的习题，并给出部分习题的解答，可使学生加深对基本原理的理解并增强应用能力。
　　本书主要介绍形式语言、自动机、可计算性和相关内容。主要内容包括：计算理论导引、有穷自动机、正则语言与正则文法、上下文无关语言及文法、下推自动机、图灵机、形式语言和自动机的层次结构、计算复杂性等。每节后面都给出了习题，并包含部分习题的解答，方便教学。　　PeterLinz，加利福尼亚大学戴维斯分校计算机科学系的荣誉教授，研究重点是：开发数值分析理论，以构建可靠的数值方法并将其用于科学计算中的问题求解环境的设计。Linz教授的相关著作还有ExploringNumericalMethods：AnIntroductioninScientificComputing。出版者的话
专家指导委员会
译者序
前言
第1章计算理论导引1
1.1数学预备知识和表示2
1.1.1集合2
1.1.2函数和关系3
1.1.3图和树5
1.1.4证明方法7
1.2三个基本概念l0
1.2.1语言11
1.2.2文法13
1.2.3自动机l8
1.3一些应用2l

第2章有穷自动机27
2.1确定型有穷接受器27
2.1.1确定型接受器和转换图27
2.1.2语言和dfa对应的语言29
2.1.3正则语言32
2.2非确定型有穷接受器35
2.2.1非确定型接受器的定义35
2.2.2为什么需要非确定型38
2.3确定型有穷接受器和非确定型有穷接受器的等价性4O
2.4减少有穷自动机中状态的化简45

第3章正则语言与正则文法5l
3.1正则表达式5l
3.1.1正则表达式的形式化定义5l
3.1.2和正则表达式相关的语言5l
3.2正则表达式和正则语言之间的联系55
3.2.1正则表达式表示正则语言55
3.2.2正则语言的正则表达式56
3.2.3描述简单模式的正则表达式59
3.3正则文法62
3.3.1右线性文法和左线性文法62
3.3.2右线性文法生成正则语言63
3.3.3正则语言的右线性文法64
3.3.4正则语言和正则文法的等价性66

第4章正则语言的性质69
4.1正则语言的封闭性质69
4.1.1简单集合运算的封闭性7O
4.1.2其他运算的封闭性7l
4.2正则语言的基本问题77
4.3识别非正则语言78
4.3.1使用鸽巢原理79
4.3.2泵引理79

第5章上下文无关语言85
5.1上下文无关文法85
5.1.1上下文无关语言的例子86
5.1.2最左推导和最右推导87
5.1.3推导树88
5.1.4句型和推导树之间的关系89
5.2分析和二义性92
5.2.1分析和成员资格判定92
5.2.2文法和语言的二义性95
5.3上下文无关文法和程序设计语言99

第6章上下文无关文法的化简与范式101
6.1文法变换方法101
6.1.1一个有用的代入规则101
6.1.2删除无用产生式103
6.1.3消除九产生式106
6.1.4消除单位产生式107
6.2两个重要的范式111
6.2.1乔姆斯基范式112
6.2.2格里巴克范式114
6.3上下文无关文法的成员资格判定算法116

第7章下推自动机119
7.1非确定型下推自动机119
7.1.1下推自动机的定义120
7.1.2下推自动机接受的语言121
7.2下推自动机与上下文无关语言125
7.2.1上下文无关语言相应的下推自动机125
7.2.2下推自动机相应的上下文无关文法129
7.3确定型下推自动机和确定型上下文无关语言133
7.4确定型上下文无关语言的文法136

第8章上下文无关语言的性质141
8.1两个泵引理141
8.1.1上下文无关语言的泵引理141
8.1.2线性语言的泵引理144
8.2上下文无关语言的封闭性质和判定算法146
8.2.1上下文无关语言的封闭性质146
8.2.2上下文无关语言的可判定性质149

第9章图灵机153
9.1标准图灵机153
9.1.1图灵机的定义153
9.1.2作为语言接受器的图灵机157
9.1.3作为转换器的图灵机160
9.2完成复杂任务的组合图灵机164
9.3图灵论题168

第10章图灵机的其他模型171
10.1对图灵机的较小修改171
10.1.1自动机类的等价性171
10.1.2带不动选择的图灵机172
10.1.3单向无穷带图灵机174
10.1.4离线图灵机175
10.2具有更复杂存储的图灵机177
10.2.1多带图灵机177
10.2.2多维图灵机179
10.3非确定型图灵机181
10.4通用图灵机183
10.5线性有界自动机186

第11章形式语言和自动机的层次结构189
11.1递归语言和递归可枚举语言189
11.1.1非递归可枚举的语言190
11.1.2非递归可枚举语言191
11.1.3递归可枚举但非递归的语言192
11.2无限制文法193
11.3上下文相关文法和语言198
11.3.1上下文相关语言和线性有界自动机198
11.3.2递归语言和上下文相关语言的关系199
11.4乔姆斯基层次结构201

第12章算法计算的限制205
12.1图灵机所不能解决的问题205
12.1.1可计算性和可判定性205
12.1.2图灵机停机问题206
12.1.3将一个不可判定问题简化成另外一个问题208
12.2递归可枚举语言的不可判定问题211
12.3波斯特对应问题2l3
12.4上下文无关语言的不可判定问题2l8

第13章其他的计算模型223
13.1递归函数224
13.1.1原始递归函数225
13.1.2Ackermann函数227
13.1.3递归函数228
13.2波斯特系统229
13.3重写系统232
13.3.1矩阵文法232
13.3.2马尔科夫算法233
13.3.3L系统234

第14章计算复杂性介绍237
14.1计算的效率237
14.2图灵机和复杂性239
14.3语言族和复杂性类241
14.4复杂性类P和NP243
部分习题的解答和提示247
参考文献283
索引285
内容简介:
　　主要介绍形式语言、自动机、可计算性和相关内容。本书特别注意定义、定理的准确性和严格性，在定理的证明中给出了直观的动机和框架，避免多余的数学细节，这有利于培养学生形式化和严格的数学推理能力，加强对问题的理解；本书通过精心设计的大量示例，生动剖析了各种定理和定义，概念清晰，深入浅出。每章后面还给出了难度不同的习题，并给出部分习题的解答，可使学生加深对基本原理的理解并增强应用能力。
　　本书主要介绍形式语言、自动机、可计算性和相关内容。主要内容包括：计算理论导引、有穷自动机、正则语言与正则文法、上下文无关语言及文法、下推自动机、图灵机、形式语言和自动机的层次结构、计算复杂性等。每节后面都给出了习题，并包含部分习题的解答，方便教学。
作者简介:
　　PeterLinz，加利福尼亚大学戴维斯分校计算机科学系的荣誉教授，研究重点是：开发数值分析理论，以构建可靠的数值方法并将其用于科学计算中的问题求解环境的设计。Linz教授的相关著作还有ExploringNumericalMethods：AnIntroductioninScientificComputing。
目录:
出版者的话
专家指导委员会
译者序
前言
第1章计算理论导引1
1.1数学预备知识和表示2
1.1.1集合2
1.1.2函数和关系3
1.1.3图和树5
1.1.4证明方法7
1.2三个基本概念l0
1.2.1语言11
1.2.2文法13
1.2.3自动机l8
1.3一些应用2l

第2章有穷自动机27
2.1确定型有穷接受器27
2.1.1确定型接受器和转换图27
2.1.2语言和dfa对应的语言29
2.1.3正则语言32
2.2非确定型有穷接受器35
2.2.1非确定型接受器的定义35
2.2.2为什么需要非确定型38
2.3确定型有穷接受器和非确定型有穷接受器的等价性4O
2.4减少有穷自动机中状态的化简45

第3章正则语言与正则文法5l
3.1正则表达式5l
3.1.1正则表达式的形式化定义5l
3.1.2和正则表达式相关的语言5l
3.2正则表达式和正则语言之间的联系55
3.2.1正则表达式表示正则语言55
3.2.2正则语言的正则表达式56
3.2.3描述简单模式的正则表达式59
3.3正则文法62
3.3.1右线性文法和左线性文法62
3.3.2右线性文法生成正则语言63
3.3.3正则语言的右线性文法64
3.3.4正则语言和正则文法的等价性66

第4章正则语言的性质69
4.1正则语言的封闭性质69
4.1.1简单集合运算的封闭性7O
4.1.2其他运算的封闭性7l
4.2正则语言的基本问题77
4.3识别非正则语言78
4.3.1使用鸽巢原理79
4.3.2泵引理79

第5章上下文无关语言85
5.1上下文无关文法85
5.1.1上下文无关语言的例子86
5.1.2最左推导和最右推导87
5.1.3推导树88
5.1.4句型和推导树之间的关系89
5.2分析和二义性92
5.2.1分析和成员资格判定92
5.2.2文法和语言的二义性95
5.3上下文无关文法和程序设计语言99

第6章上下文无关文法的化简与范式101
6.1文法变换方法101
6.1.1一个有用的代入规则101
6.1.2删除无用产生式103
6.1.3消除九产生式106
6.1.4消除单位产生式107
6.2两个重要的范式111
6.2.1乔姆斯基范式112
6.2.2格里巴克范式114
6.3上下文无关文法的成员资格判定算法116

第7章下推自动机119
7.1非确定型下推自动机119
7.1.1下推自动机的定义120
7.1.2下推自动机接受的语言121
7.2下推自动机与上下文无关语言125
7.2.1上下文无关语言相应的下推自动机125
7.2.2下推自动机相应的上下文无关文法129
7.3确定型下推自动机和确定型上下文无关语言133
7.4确定型上下文无关语言的文法136

第8章上下文无关语言的性质141
8.1两个泵引理141
8.1.1上下文无关语言的泵引理141
8.1.2线性语言的泵引理144
8.2上下文无关语言的封闭性质和判定算法146
8.2.1上下文无关语言的封闭性质146
8.2.2上下文无关语言的可判定性质149

第9章图灵机153
9.1标准图灵机153
9.1.1图灵机的定义153
9.1.2作为语言接受器的图灵机157
9.1.3作为转换器的图灵机160
9.2完成复杂任务的组合图灵机164
9.3图灵论题168

第10章图灵机的其他模型171
10.1对图灵机的较小修改171
10.1.1自动机类的等价性171
10.1.2带不动选择的图灵机172
10.1.3单向无穷带图灵机174
10.1.4离线图灵机175
10.2具有更复杂存储的图灵机177
10.2.1多带图灵机177
10.2.2多维图灵机179
10.3非确定型图灵机181
10.4通用图灵机183
10.5线性有界自动机186

第11章形式语言和自动机的层次结构189
11.1递归语言和递归可枚举语言189
11.1.1非递归可枚举的语言190
11.1.2非递归可枚举语言191
11.1.3递归可枚举但非递归的语言192
11.2无限制文法193
11.3上下文相关文法和语言198
11.3.1上下文相关语言和线性有界自动机198
11.3.2递归语言和上下文相关语言的关系199
11.4乔姆斯基层次结构201

第12章算法计算的限制205
12.1图灵机所不能解决的问题205
12.1.1可计算性和可判定性205
12.1.2图灵机停机问题206
12.1.3将一个不可判定问题简化成另外一个问题208
12.2递归可枚举语言的不可判定问题211
12.3波斯特对应问题2l3
12.4上下文无关语言的不可判定问题2l8

第13章其他的计算模型223
13.1递归函数224
13.1.1原始递归函数225
13.1.2Ackermann函数227
13.1.3递归函数228
13.2波斯特系统229
13.3重写系统232
13.3.1矩阵文法232
13.3.2马尔科夫算法233
13.3.3L系统234

第14章计算复杂性介绍237
14.1计算的效率237
14.2图灵机和复杂性239
14.3语言族和复杂性类241
14.4复杂性类P和NP243
部分习题的解答和提示247
参考文献283
索引285

查看详情

其他版本 / 全部 (2)

机械工业出版社2004-11
Jones & Bartlett Publishers2000-10

3

形式语言与自动机导论

九品

一得书苑

河北省邯郸市

当日发货成功完成率96.14%

￥288.00

券

100减20

立即购买加入购物车
14

形式语言与自动机导论有笔记划线

八品

潇洒的书阁

湖北省武汉市

平均发货5小时成功完成率96.91%

￥40.00

券

100减20

立即购买加入购物车
6

形式语言与自动机导论书有缺陷，请注意描述，认可后再拍

2005-09 印刷
印次: 1

八品

淘书书店

浙江省杭州市

平均发货18小时成功完成率95.16%

￥30.00

券

100减20

立即购买加入购物车不属于本条目
形式语言与自动机导论【正版可开发票】

全新

雅逸阁书店

海南省海口市

平均发货13小时成功完成率90.78%

￥374.00

券

100减20

立即购买加入购物车不属于本条目
4

形式语言与自动机导论无笔记划线！

九品

每日一读书店

陕西省西安市

平均发货6小时成功完成率95.26%

￥120.00

券

100减20

立即购买加入购物车
11

形式语言与自动机导论部分笔记划线多，介意勿拍，不差页

八品

海洋博文书店

重庆市沙坪坝区

平均发货6小时成功完成率95.79%

￥50.00

券

100减20

立即购买加入购物车
6

形式语言与自动机导论正版书无笔迹

九品

小熊书店

北京市大兴区

平均发货5小时成功完成率95.98%

￥275.00

券

100减20

立即购买加入购物车
9

形式语言与自动机导论

八五品

半部华夏史

平均发货18小时成功完成率86.57%

￥99.00

券

100减20

立即购买加入购物车
3

形式语言与自动机导论原书第三版认准正版，封面有实标

八五品

成人美书籍铺

上海市杨浦区

￥79.99

券

100减20

立即购买加入购物车不属于本条目

形式语言与自动机导论

内容简介:

作者简介:

目录: