形式語言，自動機理論與計算導論

內容概要

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

作者簡介

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

書籍目錄

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

章節(jié)摘錄

版權頁：插圖：

編輯推薦

《形式語言,自動機理論與計算導論》是國外計算機科學教材系列。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    形式語言，自動機理論與計算導論 PDF格式下載

---