語言與機(jī)器

內(nèi)容概要

本書是計(jì)算理論方面的優(yōu)秀教材之一，包括上下文無關(guān)文法、上下文無關(guān)文法范式、有限自動(dòng)機(jī)、正則語言的性質(zhì)、下推自動(dòng)機(jī)和上下文無關(guān)語言、圖靈機(jī)、圖靈可計(jì)算函數(shù)、喬姆斯基層次、判定問題與丘奇圖靈機(jī)、不可判定性、Mu-遞歸函數(shù)、時(shí)間復(fù)雜性、庫克定理、NP-完全問題、LL(k)文法以及LR(k)文法等問題。本書不僅介紹了計(jì)算機(jī)科學(xué)的基礎(chǔ)，而且通過概念的嚴(yán)格表述，以及使用通俗的例子來闡釋定理，從而幫助學(xué)生提高數(shù)學(xué)論證能力以及對計(jì)算理論知識的全面深入的理解。書中每章后面都有附有大量習(xí)題，通過完成這些習(xí)題，學(xué)生可以加深對本章內(nèi)容的理解。    本書可以用作計(jì)算機(jī)科學(xué)、計(jì)算機(jī)工程及其相關(guān)專業(yè)的教材，也可以作為從事計(jì)算理論、形式語言以及計(jì)算機(jī)系統(tǒng)研發(fā)的研究人員和工程技術(shù)人員的參考書。

作者簡介

Thomas A．Sudkamp是美國萊特州立大學(xué)計(jì)算機(jī)科學(xué)及工程系的教授，他的研究領(lǐng)域
廣泛，包括近似推理、人工智能、數(shù)理邏輯、建模軟計(jì)算的應(yīng)用、復(fù)雜問題領(lǐng)域的決策制定以及不確定、不精確信息和知識發(fā)掘的機(jī)器學(xué)習(xí)。Sudkamp教授目前還擔(dān)任IEEE Transactions on System，Man，a

書籍目錄

出版者的話專家指導(dǎo)委員會譯者序前言緒論第一部分  基礎(chǔ)  第1章  數(shù)學(xué)預(yù)備知識  　1.1　集合論  　1.2　笛卡兒積、關(guān)系和函數(shù)  　1.3　等價(jià)關(guān)系  　1.4　可數(shù)集合和不可數(shù)集合  　1.5　對角化和自反  　1.6　遞歸定義  　1.7　數(shù)學(xué)歸納  　1.8　有向圖  　1.9　練習(xí)  　參考文獻(xiàn)注釋  第2章  語言  　2.1　字符串和語言  　2.2　語言的有窮規(guī)格說明  　2.3　正則集合和表達(dá)式  　2.4　正則表達(dá)式和文本搜索  　2.5　練習(xí)  參考文獻(xiàn)注釋第二部分  文法、自動(dòng)機(jī)和語言  第3章  上下文無關(guān)文法  　3.1　上下文無關(guān)文法和語言  　3.2　文法和語言的例子  　3.3　正則文法  　3.4　驗(yàn)證文法  　3.5　最左推導(dǎo)和二義性  　3.6　上下文無關(guān)文法和編程語言定義  　3.7　練習(xí)  　參考文獻(xiàn)注釋  第4章  上下文無關(guān)文法范式  　4.1　文法轉(zhuǎn)換  　4.2　消去入規(guī)則  　4.3　去掉鏈規(guī)則  　4.4　無用符  　4.5　喬姆斯基范式  　4.6　CYK算法  　4.7　去掉直接左遞歸  　4.8　格立巴赫范式  　4.9　練習(xí)  　參考文獻(xiàn)注釋  第5章  有限自動(dòng)機(jī)  　5.1  一個(gè)有限狀態(tài)自動(dòng)機(jī)  　5.2  確定型有限自動(dòng)機(jī)  　5.3  狀態(tài)圖和例子  　5.4  非確定型有限自動(dòng)機(jī)  　5.5  λ-轉(zhuǎn)換  　5.6  去掉非確定性  　5.7  DFA的最小化  　5.8  練習(xí)  　參考文獻(xiàn)注釋  第6章  正則語言的性質(zhì)  　6.1  有限狀態(tài)機(jī)接收正則語言  　6.2  表達(dá)式圖  　6.3  正則文法和有限自動(dòng)機(jī)  　6.4  正則語言的封閉性質(zhì)  　6.5  非正則語言  　6.6  規(guī)則語言的泵引理  　6.7  Myhill-Nerode定理  　6.8  練習(xí)  　參考文獻(xiàn)注釋  第7章  下推自動(dòng)機(jī)和上下文無關(guān)語言    7.1  下推自動(dòng)機(jī)    7.2  PDA的變種    7.3  上下文無關(guān)語言的接收    7.4  上下文無關(guān)語言的泵引理    7.5  上下文無關(guān)語言的封閉性    7.6　練習(xí)    參考文獻(xiàn)注釋第三部分  可計(jì)算性  第8章  圖靈機(jī)    8.1　標(biāo)準(zhǔn)圖靈機(jī)    8.2　作為語言接收器的圖靈機(jī)    8.3　可供選擇接收標(biāo)準(zhǔn)    8.4　多道圖靈機(jī)    8.5　雙向圖靈機(jī)    8.6　多帶圖靈機(jī)    8.7　非確定型圖靈機(jī)    8.8　用來枚舉語言的圖靈機(jī)    8.9　練習(xí)    參考文獻(xiàn)注釋  第9章  圖靈可計(jì)算函數(shù)    9.1　函數(shù)的計(jì)算    9.2　數(shù)值計(jì)算    9.3　圖靈機(jī)的順序操作    9.4　函數(shù)的合成    9.5　不可計(jì)算函數(shù)    9.6　關(guān)于編程語言    9.7　練習(xí)    參考文獻(xiàn)注釋  第10章  喬姆斯基層次    10.1　無限制文法    10.2　上下文有關(guān)文法    10.3　線性有界自動(dòng)機(jī)    10.4　喬姆斯基層次    10.5　練習(xí)    參考文獻(xiàn)注釋  第11章  判定問題與丘奇—圖靈論題    11.1　判定問題的描述    11.2　判定問題和遞歸語言    11.3　問題歸約    11.4　丘奇—圖靈論題    11.5　通用機(jī)    11.6　練習(xí)    參考文獻(xiàn)注釋  第12章  不可判定性    12.1　圖靈機(jī)的停機(jī)問題    12.2　問題歸約和不可判定性    12.3　其他的停機(jī)問題    12.4　萊斯定理    12.5　不可解決的詞問題    12.6　波斯特對應(yīng)問題    12.7　上下文無關(guān)文法中的不可判定問題    12.8　練習(xí)    參考文獻(xiàn)注釋  第13章  Mu-遞歸函數(shù)    13.1　原始遞歸函數(shù)    13.2　一些原始遞歸函數(shù)    13.3　有界操作符    13.4　除法函數(shù)    13.5　歌德爾數(shù)字和串值遞歸    13.6　可計(jì)算部分函數(shù)    13.7  圖靈可計(jì)算函數(shù)和Mu-遞歸函數(shù)    13.8　修訂的丘奇—圖靈論題    13.9　練習(xí)    參考文獻(xiàn)注釋第四部分　計(jì)算復(fù)雜性  第14章  時(shí)間復(fù)雜性    14.1　復(fù)雜性度量    14.2　增長的速度    14.3　圖靈機(jī)的時(shí)問復(fù)雜性    14.4　復(fù)雜性和圖靈機(jī)的變種    14.5　線性加速    14.6　語言時(shí)間復(fù)雜性的屬性    14.7　計(jì)算機(jī)計(jì)算的模擬    14.8　練習(xí)    參考文獻(xiàn)注釋  第15章  P、NP和庫克定理    15.1  非確定型圖靈機(jī)的時(shí)間復(fù)雜性    15.2　P類和NP類    15.3　問題表示和復(fù)雜性    15.4　判定問題和復(fù)雜性類    15.5　哈密爾頓回路問題    15.6　多項(xiàng)式時(shí)間歸約    15.7  P=NP？    15.8  可滿足性問題    15.9  復(fù)雜類的關(guān)系    15.10　練習(xí)    參考文獻(xiàn)注釋  第16章  NP-完全問題    16.1　歸約和NP-完全問題    16.2　三元可滿足性問題    16.3　三元可滿足性的歸約    16.4　歸約和子問題    16.5　最優(yōu)化問題    16.6　近似算法    16.7　近似方案    16.8　練習(xí)    參考文獻(xiàn)注釋  第17章  其他復(fù)雜性類    17.1  派生的復(fù)雜性類    17.2  空間復(fù)雜性    17.3  空間復(fù)雜性和時(shí)間復(fù)雜性的關(guān)系    17.4  P-空間，NP-空間和薩維奇定理    17.5  P-空間完全性    17.6  一個(gè)難解問題    17.7  練習(xí)    參考文獻(xiàn)注釋第五部分　確定型語法分析  第18章　語法分析引論    18.1  文法圖    18.2　自頂向下語法分析    18.3　歸約和自底向上語法分析    18.4　自底向上語法分析器    18.5　語法分析和編譯    18.6　練習(xí)    參考文獻(xiàn)注釋  第19章　LL(k)文法    19.1 上下文無關(guān)文法中的預(yù)讀    19.2  FIRST集合、FOLLOW集合和預(yù)讀集合  　19.3  強(qiáng)LL(k)語法  　19.4  FIRSTk集合的構(gòu)造  　19.5  FOLLOWk集合的構(gòu)造  　19.6  強(qiáng)LL(1)文法  　19.7  強(qiáng)LL(k)分析器  　19.8  LL(k)文法  　19.9  練習(xí)  　參考文獻(xiàn)注釋  第20章  LR(k)文法    20.1  LR(0)上下文    20.2  LR(0)分析器    20.3  LR(0)機(jī)    20.4  被LR(0)機(jī)接收    20.5  LR(1)文法    20.6  練習(xí)    參考文獻(xiàn)注釋附錄Ⅰ  標(biāo)記索引附錄Ⅱ  希臘字母表附錄Ⅲ  ASC Ⅱ字符集附錄Ⅲ  Java的BNF范式定義參考文獻(xiàn)索引

章節(jié)摘錄

　　第1章 數(shù)學(xué)預(yù)備知識　　集合論和離散數(shù)學(xué)為形式語言理論、可計(jì)算性理論和計(jì)算復(fù)雜性分析提供了數(shù)學(xué)基礎(chǔ)。我們首先回顧集合論的表示和基本操作。集合的基數(shù)度量集合的大小，并提供無窮集合大小的準(zhǔn)確定義。德國數(shù)學(xué)家George Cantor深入研究集合的屬性后得出一條有趣的結(jié)論，就是存在不同大小的無窮集。盡管Cantor的工作僅僅表明存在一個(gè)完整的無窮集合規(guī)模層次，但是這已經(jīng)足夠支持我們把無窮集合分成兩類的目的了。這兩類分別是可數(shù)的和不可數(shù)的。如果集合的元素?cái)?shù)目與自然數(shù)一樣多，那么這個(gè)集合是可數(shù)的無窮集。如果元素?cái)?shù)目比自然數(shù)多，就是不可數(shù)無窮集。 ．　　在本章中，我們將使用對角化論證(diagonalization argument)結(jié)構(gòu)來證明定義在自然數(shù)集合上的函數(shù)集合是不可數(shù)無窮集。我們在有效過程(effective procedure)和可計(jì)算函數(shù)(computable func—tion)的意義上達(dá)成共識后(這也是本書第三部分的主要目的)，將能夠確定可以用算法計(jì)算的函數(shù)集合的大小。通過比較這兩個(gè)集合的大小，就可以證明存在這樣的函數(shù)，它們的值不能使用任何算法過程計(jì)算得到。　　一個(gè)集合可能由任意一組對象組成，我們對那些機(jī)械化生成元素的集合感興趣。然后，我們介紹可以產(chǎn)生集合元素的遞歸定義；接著構(gòu)造遞歸生成的集合與數(shù)學(xué)歸納法之間的關(guān)系。歸納已經(jīng)被證明能夠?yàn)檫f歸產(chǎn)生的無窮集合中的元素性質(zhì)提供一個(gè)通用的證明技巧。　　在本章的最后，我們將復(fù)習(xí)有向圖和樹等知識，這是貫穿本書的兩種結(jié)構(gòu)，并以圖形方式的解釋了形式語言理論和計(jì)算理論的概念?！　　?/pre>




編輯推薦
　　《語言與機(jī)器：計(jì)算機(jī)科學(xué)理論的導(dǎo)論（原書第3版）》不僅介紹了計(jì)算機(jī)科學(xué)的基礎(chǔ)，探討了算法計(jì)算的能力和局限；而且還通過概念的嚴(yán)格表述，以及使用通俗的例子來解釋定理，從而幫助學(xué)生提高數(shù)學(xué)論證能力。書中每章后面都有一些練習(xí)，通過這些練習(xí)使學(xué)生加深對本章內(nèi)容的理解。





圖書封面



圖書標(biāo)簽Tags
無




評論、評分、閱讀與下載



還沒讀過(46)
勉強(qiáng)可看(336)
一般般(573)
內(nèi)容豐富(2378)
強(qiáng)力推薦(195)


 


    語言與機(jī)器 PDF格式下載