上下文无关语言的数学理论查看源代码讨论查看历史

原图链接来自 孔夫子旧书网 的图片

《上下文无关语言的数学理论》，形式语言专著。S.金斯伯格著。1966年纽约Mc Gram Hill出版社出版。中译本山东大学出版社1986年出版，陈力行译。

本书收编于《世界百科名著大辞典》。

内容简介

本书共6章，约26万字。第1章介绍了上下文无关文法、上下文无关语言、派生树和歧义性等基本概念。第2章讨论了正规集合，有穷状态接受器，和下推接受器。给出正规集合用右线性 (或左线性) 文法的描述，和上下文无关语言用下推接受器的描述。第3章介绍了保上下文无关语言的运算。第4章涉及了可解性与不可解性。主要结果是下述几条的递归不可解性: 1.两个上下文无关文法是否生成同一个上下文无关语言;2.是否存在一个广义时序机把任意给定的上下文无关语言非平凡的映射到另一个任意给定的上下文无关语言，3.任意上下文无关语言是否是歧义的。第5章讨论了有界语言和半线性集合。特别证明了关于把上下文无关语言映射到半线性集合上的Parikh的结果，描述了有界上下文无关语言，并导出了证明某个集合为非语言的方法。第6章研究了先天歧义性，并给出了一个有界上下文无关语言是先天歧义的代数的充分必要条件，也给出了确定任意上下文无关语言是否先天歧义的递归不可解性。

全书专设1章复习必要的数学知识。每章末尾列有历史参考资料。还包含有相当数量的习题。它们不仅能使对课文有更好的理解，并且包括了这个理论的一些次要论题。许多习题是从公开出版的文献中，或为众所周知但未公开出版的文献中取来的。有一些是相当复杂，或者是较为困难的。一些尚待解决的问题和思考题分布在全书各处，以指示这一学科另外一些发展方向。本书内容充实，推理严谨。适合于计算机科学、语言学、数学、逻辑学，甚至理论生物学的大学生，研究生和有关工作者参阅。

作者简介

S. 金斯伯格 (S.Ginsburg)，教授，现执教于美国洛杉矶南加利福尼亚大学计算机科学系。

相关信息

《世界百科名著大辞典》以“齐全、新颖、系统、科学、稳定”为编纂原则，选收了1985年以前出版的自然科学、技术科学、综合性科学、社会和人文科学、文学艺术等方面500多个学科(包括主要学科及其分支学科)的名著，以及世界各大宗教的重要典籍。其中有科学上各主要学派的代表作，文学艺术上各主要流派的代表作，宗教上各主要宗派的主要典籍；世界上大多数国家和地区的重要著作。

视频

上下文无关语言的数学理论 相关视频

1.结构的形式语言 2.材质的形式语言（1）