形式語言，自動機(jī)理論與計算導(dǎo)論

內(nèi)容概要

　　形式語言與自動機(jī)理論是計算機(jī)科學(xué)與技術(shù)專業(yè)的一門重要課程。本書是作者結(jié)合其多年來在大學(xué)講授該門課程的經(jīng)驗和體會，選擇和組織有關(guān)內(nèi)容撰寫而成。不僅含有有關(guān)正則語言、上下文無關(guān)語言的文法、識別模型及其性質(zhì)、圖靈機(jī)的基本知識，更涉及到本學(xué)科方法論中所包含的3個學(xué)科形態(tài)。其內(nèi)容特點是抽象和形式化，既有嚴(yán)格的理論證明，又具有很強(qiáng)的構(gòu)造性，從而培養(yǎng)學(xué)生的形式化描述和抽象思維能力，使學(xué)生了解和初步掌握“問題、形式化、自動化（計算機(jī)化）”的解題思路。

作者簡介

作者：(印度)卡馬拉(Kamala Krithivasan) (印度)拉瑪(Rama R) 譯者：孟宇龍 李健利 王宇華 合著者：馮曉寧卡馬拉，Kamala Krithivasan，馬德拉斯大學(xué)博士，1975年進(jìn)入印度理工學(xué)院馬德拉斯分校( IIMT)參加工作。計算機(jī)科學(xué)與工程學(xué)院教授，1992-1995年擔(dān)任院長，在IIMT有著30余年的教學(xué)和研究經(jīng)驗。她的研究方向包括形式語言理論、非傳統(tǒng)模型計算(如DNA計算)、膜計算以及離散分層計算等。Kamala教授是1986年福爾布萊特學(xué)術(shù)獎金的獲得者，同時還是印度國家工程學(xué)會的會員。Rama R，1989年在安娜大學(xué)獲得博士學(xué)位。進(jìn)入印度理工學(xué)院馬德拉斯分校(IIMT)擔(dān)任副教授之前，曾在安娜大學(xué)工程學(xué)院任教。2006年晉職為教授并任教至今。Rama教授擁有20余年的教學(xué)和研究經(jīng)驗，并且指導(dǎo)過四位研究生的博士論文。她的研究領(lǐng)域是形式語言與自動機(jī)和自然計算。同時，她也是印度工業(yè)教育學(xué)會的終身會員。

書籍目錄

第1章 基礎(chǔ)知識
　1.1 集合, 關(guān)系和函數(shù)
　1.2 證明方法
　1.3 圖
　1.4 語言：基本概念
　問題與解答
　習(xí)題
第2章 文法
　2.1 文法的定義和分類
　2.2 二義性
　2.3 CFG 的化簡
　2.4 范式
　問題和解答
　習(xí)題
第3章 有限狀態(tài)自動機(jī)
　3.1 確定有限狀態(tài)自動機(jī)(DFSA)
　3.2 不確定有限狀態(tài)自動機(jī)(NFSA)
　3.3 正則表達(dá)式
　問題與解答
　習(xí)題
第4章 有限自動機(jī)：特征、性質(zhì)和可判定性
　4.1 有限自動機(jī)和正則文法
　4.2 正則集的泵浦引理
　4.3 封閉性
　4.4 可判定性定理
　問題和解答
　習(xí)題
第5章 帶輸出的有限狀態(tài)自動機(jī)及其最小化
　5.1 Myhill鄄Nerode 定理
　5.2 帶輸出的有限自動機(jī)
　問題與解答
　習(xí)題
第6章 有限自動機(jī)的變形
　6.1 雙向有限自動機(jī)
　6.2 多頭有限狀態(tài)自動機(jī)
　6.3 概率有限自動機(jī)
　6.4 加權(quán)有限自動機(jī)和數(shù)字圖像
　問題與解答
　習(xí)題
第7章 下推自動機(jī)
　7.1 下推自動機(jī)
　7.2 空棧接受和終態(tài)接受的等價
　7.3 CFG 和PDA 的等價
　問題與解答
　習(xí)題
第8章 上下文無關(guān)文法性質(zhì)與分析
　8.1 CFL 的泵引理
　8.2 CFL 的封閉性
　8.3 CFL 的判定性質(zhì)
　8.4 CFL 的子群
　8.5 帕里克映射與帕里克定理
　8.6 自嵌入性
　8.7 同態(tài)下的特性
　問題與解答
　習(xí)題
第9章 圖靈機(jī)
　9.1 作為接受器的圖靈機(jī)
　9.2 作為計算設(shè)備的圖靈機(jī)
　9.3 圖靈機(jī)的構(gòu)造技術(shù)
　問題與解答
　習(xí)題
第10章 圖靈機(jī)的變形
　10.1 通用版本
　10.2 受限圖靈機(jī)
　10.3 作為枚舉器的圖靈機(jī)
　10.4 圖靈機(jī)和0 型語言的等價
　10.5 線性有界自動機(jī)
　10.6 歌德爾編號
　問題與解答
　習(xí)題
第11章 通用圖靈機(jī)及可判定性
　11.1 圖靈機(jī)的編碼和枚舉
　11.2 遞歸和遞歸可枚舉集
　11.3 通用圖靈機(jī)
　11.4 問題, 實例和語言
　11.5 萊斯定理
　11.6 規(guī)約問題以證明不可判定性
　11.7 波斯特對應(yīng)問題
　11.8 可計算函數(shù)
　問題與解答
　習(xí)題
第12章 時間與空間復(fù)雜度
　12.1 RAM 模型
　12.2 圖靈機(jī)的時間與帶復(fù)雜度
　問題與解答
　習(xí)題
第13章 最近的趨勢及應(yīng)用
　13.1 正則重寫
　13.2 馬庫斯上下文文法
　13.3 林登麥伊爾系統(tǒng)
　13.4 文法系統(tǒng)及分布式自動機(jī)
第14章 一些新的計算模型
　14.1 DNA 計算
　14.2 膜計算
單項選擇題(I)
單項選擇題(II)
參考文獻(xiàn)
　　

章節(jié)摘錄

版權(quán)頁：插圖：

編輯推薦

《形式語言,自動機(jī)理論與計算導(dǎo)論》是國外計算機(jī)科學(xué)教材系列。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    形式語言，自動機(jī)理論與計算導(dǎo)論 PDF格式下載

---