上下文無關語言的數學理論檢視原始碼討論檢視歷史

原圖鏈接來自 孔夫子舊書網 的圖片

《上下文無關語言的數學理論》，形式語言專著。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）