语言与机器:计算机科学理论导论(原书第3版)
点击看大图
基本信息
编辑推荐
理论计算机科学是推动计算机技术和应用向前发展的巨大动力。形式语言、自动机、可计算性、计算复杂性和相关方面内容构成的计算理论，是理论计算机科学的基础内容之一。本书由美国莱特州立大学计算机科学及工程系的Thomas A.Sudkamp教授编写，是介绍这些内容的优秀教材。 全书不仅介绍了计算机科学的基础，探讨了算法计算的能力和局限；而且还通过概念的严格表述，以及使用通俗的例子来解释定理，从而帮助学生提高数学论证能力。书中每章后面都有一些练习，通过这些练习使学生加深对本章内容的理解。
内容简介回到顶部↑
书籍
计算机书籍
本书是计算理论方面的优秀教材之一，包括上下文无关文法、上下文无关文法范式、有限自动机、正则语言的性质、下推自动机和上下文无关语言、图灵机、图灵可计算函数、乔姆斯基层次、判定问题与丘奇图灵机、不可判定性、mu-递归函数、时间复杂性、库克定理、np-完全问题、ll(k)文法以及lr(k)文法等问题。本书不仅介绍了计算机科学的基础，而且通过概念的严格表述，以及使用通俗的例子来阐释定理，从而帮助学生提高数学论证能力以及对计算理论知识的全面深入的理解。书中每章后面都有附有大量习题，通过完成这些习题，学生可以加深对本章内容的理解。
本书可以用作计算机科学、计算机工程及其相关专业的教材，也可以作为从事计算理论、形式语言以及计算机系统研发的研究人员和工程技术人员的参考书。
计算机书籍
本书是计算理论方面的优秀教材之一，包括上下文无关文法、上下文无关文法范式、有限自动机、正则语言的性质、下推自动机和上下文无关语言、图灵机、图灵可计算函数、乔姆斯基层次、判定问题与丘奇图灵机、不可判定性、mu-递归函数、时间复杂性、库克定理、np-完全问题、ll(k)文法以及lr(k)文法等问题。本书不仅介绍了计算机科学的基础，而且通过概念的严格表述，以及使用通俗的例子来阐释定理，从而帮助学生提高数学论证能力以及对计算理论知识的全面深入的理解。书中每章后面都有附有大量习题，通过完成这些习题，学生可以加深对本章内容的理解。
本书可以用作计算机科学、计算机工程及其相关专业的教材，也可以作为从事计算理论、形式语言以及计算机系统研发的研究人员和工程技术人员的参考书。
作译者回到顶部↑
本书提供作译者介绍
Thomas A．Sudkamp是美国莱特州立大学计算机科学及工程系的教授，他的研究领域
广泛，包括近似推理、人工智能、数理逻辑、建模软计算的应用、复杂问题领域的决策制定以及不确定、不精确信息和知识发掘的机器学习。Sudkamp教授目前还担任IEEE Transactions on System，Man，and Cybemetics和IEEE Transactions on Fuzzy Systems的副编辑，International Journal of Approximate Reasonin9和Fuzzy Sets and Systems的领域编辑。他也曾经担任过北美模糊信息处理协会NAFIPS)的主席以及国际模.. << 查看详细
广泛，包括近似推理、人工智能、数理逻辑、建模软计算的应用、复杂问题领域的决策制定以及不确定、不精确信息和知识发掘的机器学习。Sudkamp教授目前还担任IEEE Transactions on System，Man，and Cybemetics和IEEE Transactions on Fuzzy Systems的副编辑，International Journal of Approximate Reasonin9和Fuzzy Sets and Systems的领域编辑。他也曾经担任过北美模糊信息处理协会NAFIPS)的主席以及国际模.. << 查看详细
目录回到顶部↑
出版者的话
专家指导委员会
译者序
前言
绪论
第一部分 基础
第1章 数学预备知识
1.1 集合论
1.2 笛卡儿积、关系和函数
1.3 等价关系
1.4 可数集合和不可数集合
1.5 对角化和自反
1.6 递归定义
1.7 数学归纳
1.8 有向图
1.9 练习
参考文献注释
第2章 语言
2.1 字符串和语言
2.2 语言的有穷规格说明
专家指导委员会
译者序
前言
绪论
第一部分 基础
第1章 数学预备知识
1.1 集合论
1.2 笛卡儿积、关系和函数
1.3 等价关系
1.4 可数集合和不可数集合
1.5 对角化和自反
1.6 递归定义
1.7 数学归纳
1.8 有向图
1.9 练习
参考文献注释
第2章 语言
2.1 字符串和语言
2.2 语言的有穷规格说明
译者序回到顶部↑
理论计算机科学是推动计算机技术和应用向前发展的巨大动力。形式语言、自动机、可计算性、计算复杂性以及相关内容构成的计算理论，是理论计算机科学的基础内容之一。学习、研究这些内容，不仅为进一步学习、研究理论计算机科学打下基础，而且对增强形式化能力和推理能力也有帮助作用，这些能力对从事计算机技术中的形式化方法、技术等研究，是不可缺少的。.
本书是由美国莱特州立大学计算机科学及工程系的Thomas A.Sudkamp教授编写的高等学校教材，主要介绍形式语言、自动机、可计算性、计算复杂性和上下文无关语言的确定性分析等内容。本书不仅介绍了计算机科学的基础，而且通过概念的严格表述，以及使用通俗的例子来阐释定理，从而期望能够帮助学生提高数学论证能力以及对计算理论知识的全面深入的理解。书中每章后面都有大量习题，通过完成这些习题，学生可以加深对本章内容的理解。本书是理论计算机科学的优秀教材之一。
本书可以用作计算机科学、计算机工程及其相关专业的教材，也可以作为从事计算理论、形式语言以及计算机系统研发的研究人员和工程技术人员的参考书。..
引进国外的优秀计算机教材，对我国的计算机教育事业的发展会起到积极的推动作用，也是与世界接轨、建立世界一流大学不可缺少的条件之一。我们把本书介绍给国内从事计算机教育事业的同行们，以供参考。
参加本书翻译的有：孙家骕同志，负责各章译稿的详细修改和全书的统稿；郝丹同志负责第1到第4章及前言的翻译；刘江红同志负责第5到第7章的翻译；程邵斌同志负责第8到第10章的翻译；李琰同志负责第11到第13章的翻译；侯姗姗同志负责第14到第17章的翻译；黄晓晨同志负责第18到第20章及附录的翻译。
由于我们的能力有限，难免有不当之处，敬请读者不吝赐教。...
译者
2007年4月
本书是由美国莱特州立大学计算机科学及工程系的Thomas A.Sudkamp教授编写的高等学校教材，主要介绍形式语言、自动机、可计算性、计算复杂性和上下文无关语言的确定性分析等内容。本书不仅介绍了计算机科学的基础，而且通过概念的严格表述，以及使用通俗的例子来阐释定理，从而期望能够帮助学生提高数学论证能力以及对计算理论知识的全面深入的理解。书中每章后面都有大量习题，通过完成这些习题，学生可以加深对本章内容的理解。本书是理论计算机科学的优秀教材之一。
本书可以用作计算机科学、计算机工程及其相关专业的教材，也可以作为从事计算理论、形式语言以及计算机系统研发的研究人员和工程技术人员的参考书。..
引进国外的优秀计算机教材，对我国的计算机教育事业的发展会起到积极的推动作用，也是与世界接轨、建立世界一流大学不可缺少的条件之一。我们把本书介绍给国内从事计算机教育事业的同行们，以供参考。
参加本书翻译的有：孙家骕同志，负责各章译稿的详细修改和全书的统稿；郝丹同志负责第1到第4章及前言的翻译；刘江红同志负责第5到第7章的翻译；程邵斌同志负责第8到第10章的翻译；李琰同志负责第11到第13章的翻译；侯姗姗同志负责第14到第17章的翻译；黄晓晨同志负责第18到第20章及附录的翻译。
由于我们的能力有限，难免有不当之处，敬请读者不吝赐教。...
译者
2007年4月
前言回到顶部↑
本书第3版的出版目的与前两版相同，即介绍计算科学理论，从而为计算机专业的初级和中级学生提供计算机科学理论的健全的数学表示。促使我对上一版进行更新的原因有三个：通过提供附加的动机介绍和例子来增强表达效果；扩大知识范围，特别是在计算复杂性这一领域；为教师讲授计算机科学理论的课程提供更多的灵活性。.
许多面向应用领域的学生质疑学习理论基础知识的重要性。然而，正是这门课强调了计算机科学问题的宏观视图。现在的编程语言和计算机体系结构很陈旧，另外，与此相关的大家感兴趣的问题都已经找到了相应的解决方案，本书中的很多内容都与这些相关。什么类型的模式可以用某种算法识别？语言如何被形式化地定义和分析？算法计算的固有能力和局限性是什么？有哪些问题的解决方法需要的时间和空间过多以至现实中无法实现？如何比较两个问题相对的困难程度？上述问题在本书中都将逐一论述。
组织
由于绝大多数本科计算机科学专业的学生都没有或缺少足够的抽象数学的基础知识，因此本书不仅介绍计算机科学的基础，而且希望能够提高学生的数学论证能力。我们通过概念的严格表述，以及使用通俗的例子来解释一些定理，来达到上述目的。每章最后都有一些练习，从而强化和加深对本章内容的理解。
为了便于大家学习，我们假设大家都没有特殊的数学预备知识。因而，第1章介绍计算理论的数学工具：基本集合理论、递归定义以及数学归纳证明。除了1.3节和1.4节介绍的特殊内容外，第1章和第2章介绍了覆盖全书的基础知识。1.3节介绍基数和对角化。它们被用在构造不确定语言和不可计算方法的存在性证明中。1.4节检查反证法中的自引用的使用。这种技术用在不确定性证明中，包括证明停机问题无解。对于那些已经学完离散数学课程的学生，第1章的大部分内容可以看作是对这些知识的复习。
考虑到计算基础的不同课程可以强调不同的主题，本书的表述和组织方式设计为允许一门课程深入探究某些特殊主题，同时提供一种加强对主要主题的研究能力，这种能力通过介绍和深入探讨计算机科学理论研究范围的材料来获取。课程的核心内容集中于形式化的自动机语言理论的经典表示，可计算性和不确定性、计算复杂性，以及作为编程语言定义和编译器设计基础的形式化语言，详见下面表格。小节后面的星号表示这部分内容可以略过但并不影响整本书表述的连贯性。带星号的小节通常包括应用的表示、相关主题的介绍或是主题中一个复杂结论的详细证明。
形式语言和自动机理论的经典表述考察了文法和乔姆斯基体系中抽象机之间的关系。本书同时也描述了确定型有限自动机、下推自动机、线性无界自动机和图灵机的可计算性性质。抽象机的计算能力的分析，是通过使用图灵机和无限制文法产生的语言，来识别语言的等价性而建立的。..
可计算性理论考察了算法问题解决的能力和局限。可计算性包括确定性和丘吉尔—图灵理论。其中，后者通过建立图灵可计算性和μ-递归函数的等价性而获得支持。对角化证明用来证明图灵机的停机问题是无解的，而问题化简则用来构造有关算法计算的一系列问题的不确定性。
对于计算复杂性的研究，我们首先考虑计算所需要的资源的度量方法。我们选取图灵机作为评估复杂性的框架，时间和空间的复杂性是通过图灵机计算中使用的转换数量和内存数量来计算的。类问题可以使用确定型图灵机在多项式时间内解决，这类问题被认为是具有有效算法解决方案的一类问题。在这之后，类问题和NP完全理论也会给与介绍。逼近算法用来获得NP完全优化问题的近似最优解。
形式化语言理论在计算科学中最重要的应用是使用文法来指定编程语言的语法。这门课程强调使用形式化技术来定义编程语言和提出有效的分解策略，它起始于用来生成语言的上下文无关文法和用于识别模式的有限自动机的介绍。介绍语言的定义之后，第18章至第20章考察了LL和LR文法以及通过这些类型的文法定义的语言的确定性分解的性质。
练习
掌握计算科学的理论基础的过程不是一场只需旁观的体育运动会。一个人只有通过解决问题，并考察主要结论的证明，才能够充分理解理论的概念、算法和精妙之处的。也就是说，对整体理解需要更多的细微努力。为了达到这一目的，我们在每章后面都编写了一些练习。这些练习包括很多方面，既有本章介绍的主题的构造练习，也有对理论的扩展。
每部分的练习中都有几个是带星号的，这些问题要比本章的其他问题更难，在本质上更理论些，或者更特别和有趣。
符号
计算科学理论是有效性计算的能力和缺陷的数学检查。与其他形式化分析类似，这种表示必须能够提供概念、结构和操作的精确且无二义性的定义。
使用罗马字母表示集合和数学结构在一定程度上不太标准，然而这样做能使得一种结构的构成成分很容易地被识别出来。例如，上下文无关文法的结构是G=(∑，V，P，S)。仅仅从字体上我们就可以看出，G包含三个集合和变量S。
整本书使用三种计数系统，每章、节、条目都给出一条引用。一个计数序列记录了定义、引理、定理、推论和算法；另一个序列用来识别例子；图、表以及练习使用章节序号来标识。
证明的结尾以■标记结束，例子的结尾以□标记结束。符号索引，包括这些符号的介绍，以及它们出现的页数都在附录I中给出。
补充
我们给出的部分练习的解答，仅仅是为了辅助教师授课。...
许多面向应用领域的学生质疑学习理论基础知识的重要性。然而，正是这门课强调了计算机科学问题的宏观视图。现在的编程语言和计算机体系结构很陈旧，另外，与此相关的大家感兴趣的问题都已经找到了相应的解决方案，本书中的很多内容都与这些相关。什么类型的模式可以用某种算法识别？语言如何被形式化地定义和分析？算法计算的固有能力和局限性是什么？有哪些问题的解决方法需要的时间和空间过多以至现实中无法实现？如何比较两个问题相对的困难程度？上述问题在本书中都将逐一论述。
组织
由于绝大多数本科计算机科学专业的学生都没有或缺少足够的抽象数学的基础知识，因此本书不仅介绍计算机科学的基础，而且希望能够提高学生的数学论证能力。我们通过概念的严格表述，以及使用通俗的例子来解释一些定理，来达到上述目的。每章最后都有一些练习，从而强化和加深对本章内容的理解。
为了便于大家学习，我们假设大家都没有特殊的数学预备知识。因而，第1章介绍计算理论的数学工具：基本集合理论、递归定义以及数学归纳证明。除了1.3节和1.4节介绍的特殊内容外，第1章和第2章介绍了覆盖全书的基础知识。1.3节介绍基数和对角化。它们被用在构造不确定语言和不可计算方法的存在性证明中。1.4节检查反证法中的自引用的使用。这种技术用在不确定性证明中，包括证明停机问题无解。对于那些已经学完离散数学课程的学生，第1章的大部分内容可以看作是对这些知识的复习。
考虑到计算基础的不同课程可以强调不同的主题，本书的表述和组织方式设计为允许一门课程深入探究某些特殊主题，同时提供一种加强对主要主题的研究能力，这种能力通过介绍和深入探讨计算机科学理论研究范围的材料来获取。课程的核心内容集中于形式化的自动机语言理论的经典表示，可计算性和不确定性、计算复杂性，以及作为编程语言定义和编译器设计基础的形式化语言，详见下面表格。小节后面的星号表示这部分内容可以略过但并不影响整本书表述的连贯性。带星号的小节通常包括应用的表示、相关主题的介绍或是主题中一个复杂结论的详细证明。
形式语言和自动机理论的经典表述考察了文法和乔姆斯基体系中抽象机之间的关系。本书同时也描述了确定型有限自动机、下推自动机、线性无界自动机和图灵机的可计算性性质。抽象机的计算能力的分析，是通过使用图灵机和无限制文法产生的语言，来识别语言的等价性而建立的。..
可计算性理论考察了算法问题解决的能力和局限。可计算性包括确定性和丘吉尔—图灵理论。其中，后者通过建立图灵可计算性和μ-递归函数的等价性而获得支持。对角化证明用来证明图灵机的停机问题是无解的，而问题化简则用来构造有关算法计算的一系列问题的不确定性。
对于计算复杂性的研究，我们首先考虑计算所需要的资源的度量方法。我们选取图灵机作为评估复杂性的框架，时间和空间的复杂性是通过图灵机计算中使用的转换数量和内存数量来计算的。类问题可以使用确定型图灵机在多项式时间内解决，这类问题被认为是具有有效算法解决方案的一类问题。在这之后，类问题和NP完全理论也会给与介绍。逼近算法用来获得NP完全优化问题的近似最优解。
形式化语言理论在计算科学中最重要的应用是使用文法来指定编程语言的语法。这门课程强调使用形式化技术来定义编程语言和提出有效的分解策略，它起始于用来生成语言的上下文无关文法和用于识别模式的有限自动机的介绍。介绍语言的定义之后，第18章至第20章考察了LL和LR文法以及通过这些类型的文法定义的语言的确定性分解的性质。
练习
掌握计算科学的理论基础的过程不是一场只需旁观的体育运动会。一个人只有通过解决问题，并考察主要结论的证明，才能够充分理解理论的概念、算法和精妙之处的。也就是说，对整体理解需要更多的细微努力。为了达到这一目的，我们在每章后面都编写了一些练习。这些练习包括很多方面，既有本章介绍的主题的构造练习，也有对理论的扩展。
每部分的练习中都有几个是带星号的，这些问题要比本章的其他问题更难，在本质上更理论些，或者更特别和有趣。
符号
计算科学理论是有效性计算的能力和缺陷的数学检查。与其他形式化分析类似，这种表示必须能够提供概念、结构和操作的精确且无二义性的定义。
使用罗马字母表示集合和数学结构在一定程度上不太标准，然而这样做能使得一种结构的构成成分很容易地被识别出来。例如，上下文无关文法的结构是G=(∑，V，P，S)。仅仅从字体上我们就可以看出，G包含三个集合和变量S。
整本书使用三种计数系统，每章、节、条目都给出一条引用。一个计数序列记录了定义、引理、定理、推论和算法；另一个序列用来识别例子；图、表以及练习使用章节序号来标识。
证明的结尾以■标记结束，例子的结尾以□标记结束。符号索引，包括这些符号的介绍，以及它们出现的页数都在附录I中给出。
补充
我们给出的部分练习的解答，仅仅是为了辅助教师授课。...
书摘回到顶部↑
第1章 数学预备知识
集合论和离散数学为形式语言理论、可计算性理论和计算复杂性分析提供了数学基础。我们首先回顾集合论的表示和基本操作。集合的基数度量集合的大小，并提供无穷集合大小的准确定义。德国数学家George Cantor深入研究集合的属性后得出一条有趣的结论，就是存在不同大小的无穷集。尽管Cantor的工作仅仅表明存在一个完整的无穷集合规模层次，但是这已经足够支持我们把无穷集合分成两类的目的了。这两类分别是可数的和不可数的。如果集合的元素数目与自然数一样多，那么这个集合是可数的无穷集。如果元素数目比自然数多，就是不可数无穷集。 ．
在本章中，我们将使用对角化论证(diagonalization argument)结构来证明定义在自然数集合上的函数集合是不可数无穷集。我们在有效过程(effective procedure)和可计算函数(computable func—tion)的意义上达成共识后(这也是本书第三部分的主要目的)，将能够确定可以用算法计算的函数集合的大小。通过比较这两个集合的大小，就可以证明存在这样的函数，它们的值不能使用任何算法过程计算得到。
一个集合可能由任意一组对象组成，我们对那些机械化生成元素的集合感兴趣。然后，我们介绍可以产生集合元素的递归定义；接着构造递归生成的集合与数学归纳法之间的关系。归纳已经被证明能够为递归产生的无穷集合中的元素性质提供一个通用的证明技巧。
在本章的最后，我们将复习有向图和树等知识，这是贯穿本书的两种结构，并以图形方式的解释了形式语言理论和计算理论的概念。
……
集合论和离散数学为形式语言理论、可计算性理论和计算复杂性分析提供了数学基础。我们首先回顾集合论的表示和基本操作。集合的基数度量集合的大小，并提供无穷集合大小的准确定义。德国数学家George Cantor深入研究集合的属性后得出一条有趣的结论，就是存在不同大小的无穷集。尽管Cantor的工作仅仅表明存在一个完整的无穷集合规模层次，但是这已经足够支持我们把无穷集合分成两类的目的了。这两类分别是可数的和不可数的。如果集合的元素数目与自然数一样多，那么这个集合是可数的无穷集。如果元素数目比自然数多，就是不可数无穷集。 ．
在本章中，我们将使用对角化论证(diagonalization argument)结构来证明定义在自然数集合上的函数集合是不可数无穷集。我们在有效过程(effective procedure)和可计算函数(computable func—tion)的意义上达成共识后(这也是本书第三部分的主要目的)，将能够确定可以用算法计算的函数集合的大小。通过比较这两个集合的大小，就可以证明存在这样的函数，它们的值不能使用任何算法过程计算得到。
一个集合可能由任意一组对象组成，我们对那些机械化生成元素的集合感兴趣。然后，我们介绍可以产生集合元素的递归定义；接着构造递归生成的集合与数学归纳法之间的关系。归纳已经被证明能够为递归产生的无穷集合中的元素性质提供一个通用的证明技巧。
在本章的最后，我们将复习有向图和树等知识，这是贯穿本书的两种结构，并以图形方式的解释了形式语言理论和计算理论的概念。
……
加载中...
