內容簡介
本書是計算理論方面的優秀教材之一，包括上下文無關文法、上下文無關文法範式、有限自動機、正則語言的性質、下推自動機和上下文無關語言、圖靈機、圖靈可計算函式、喬姆斯基層次、判定問題與丘奇圖靈機、不可判定性、Mu—遞歸函式、時間複雜性、庫克定理、NP—完全問題、LL(k)文法以及LR(k)文法等問題。本書不僅介紹了計算機科學的基礎，而且通過概念的嚴格表述，以及使用通俗的例子來闡釋定理，從而幫助學生提高數學論證能力以及對計算理論知識的全出版者的話
目錄
出版者的話
專家指導委員會
譯者序
前言
緒論
第一部分基礎
第1章數學預備知識
第2章語言
第二部分文法、自動機和語言
第3章上下文無關文法
第4章上下文無關文法範式
第5章有限自動機
第6章正則語言的性質
第7章下推自動機和上下文無關語言
第三部分可計算性
第8章圖靈機
第9章圖靈可計算函式
第10章喬姆斯基層次
第11章判定問題與丘奇圖靈機
第12章不可判定性
第13章Mu—遞歸函式
第四部分計算複雜性
第14章時間複雜性
第15章庫克定理
第16章NP—完全問題
第17章其他複雜性類
第五部分確定型語法分析
第18章語法分析引論
第19章LL(k)文法
第20章LR(k)文法
附錄
參考文獻
索引
……
