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

內(nèi)容概要

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

作者簡(jiǎn)介

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

書(shū)籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

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

---