自動機理論與應用

內(nèi)容概要

　　《自動機理論與應用》闡述了計算科學的優(yōu)美理論基礎，通過演示計算理論在現(xiàn)代硬件和軟件系統(tǒng)設計中的影響，把理論知識帶到了現(xiàn)實實踐之中。本書介紹了關鍵概念的應用，為讀者在實際工作中使用計算理論提供實際指導。本書討論的應用包括：程序設計語言、編譯器、網(wǎng)絡技術、自然語言處理、人工智能、計算生物學、安全性、博弈論、商業(yè)規(guī)則建模、標識語言、Web搜索等。本書既適合作為自動機理論課程的教程，也是相關專業(yè)人員的重要參考用書。
　　

作者簡介

作者：(美國)里奇 (Elaine Rich) 譯者：米哲偉 武桂香 等

書籍目錄

第1部分簡 介
　第1章 為什么學習計算理論
　第2章 語言與字符串
　第3章 語言層次
　第4章 計算
第2部分 有限狀態(tài)機與正則語言
　第5章 有限狀態(tài)機
　第6章 正則表達式
　第7章 正則文法
　第8章 正則與非正則語言
　第9章 正則語言的算法與決策過程
　第10章 小結(jié)與參考資料
第3部分 上下文無關語言與壓棧自動機
　第11章 上下文無關文法
　第12章 壓棧自動機
　第13章 上下文無關與非上下文無關語言
　第14章 上下文無關語言的算法與決策過程
　第15章 上下文無關解析
　第16章 小結(jié)與參考資料
第4部分 圖靈機與不可確定性
　第17章 圖靈機
　第18章 church-turing命題
　第19章 停止問題的不可解決性
　第20章 可確定與半確定語言
　第21章 可確定性與不可確定性證明
　第22章 不明顯提圖靈機問題的語言的可確定性
　第23章 無限制文法
　第24章 chomsky層次及其他
　第25章 可計算函數(shù)
　第26章 小結(jié)與參考資料
第5部分 復 雜度
　第27章 復雜度分析簡介
　第28章 時間復雜度類
　第29章 空間復雜度類
　第30章 難題的實用解
　第31章 小結(jié)與參考資料
參考資料

章節(jié)摘錄

版權頁：插圖：可以把第4部分的工作看成探索計算的極限。我們考慮了許多不同的可計算模型，這些模型試圖回答這樣的問題，“能計算什么？”其中有些模型很相似。例如，Post生產(chǎn)系統(tǒng)和無限制文法都是通過開始符和一組改寫字符串的生產(chǎn)規(guī)則來定義語言。盡管有差別（Post生產(chǎn)系統(tǒng)利用變量，要匹配整個字符串，而無限文法只用常量，可以匹配子串），但兩個形式是一致的：都定義SD語言類。同樣，圖靈機和標記系統(tǒng)也差不多，一個用磁帶和可移動的讀／寫頭，一個用先進先出隊列。但它們的差別也不大，兩都可以相互模擬。

編輯推薦

《世界著名計算機教材精選:自動機理論與應用》由清華大學出版社出版。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    自動機理論與應用 PDF格式下載

---