《形式語言，自動機理論與計算導論》是2012年2月1日由電子工業出版社出版的圖書，作者是卡馬拉(Kamala Krithivasan)、拉瑪(Rama R)，譯者是孟宇龍、李健利、王宇華。
基本介紹
- 書名：形式語言，自動機理論與計算導論
- 作者：卡馬拉(Kamala Krithivasan)、拉瑪(Rama R)
- 譯者：孟宇龍、李健利、王宇華
- ISBN：9787121153945, 7121153947
- 頁數：317頁
- 出版社：電子工業出版社
- 出版時間：2012年2月1日
- 裝幀：平裝
- 開本：16開
- 正文語種：簡體中文
內容簡介,圖書目錄,作者簡介,
內容簡介
《形式語言,自動機理論與計算導論》用簡潔清晰的方式闡述了相關理論概念，並深入涵蓋了形式文法及基本的自動機類型。同時對該領域的當前研究趨勢進行了相關概述。《形式語言,自動機理論與計算導論》概括了本學科的廣泛套用以及關於計算方面的基本定理和原理，對計算機科學與信息技術的本科課程教學具有一定價值。《形式語言,自動機理論與計算導論》特點運用大量例題來幫助讀者理解概念要點通過圖靈機詳盡闡述了可計算性和可判定性問題提出一些有助於學生進行深入研究的形式語言前沿問題及最新的計算模型設計多項選擇題以幫助學生理解基礎理論。
圖書目錄
第1章 基礎知識1
1.1 集合,關係和函式1
1.2 證明方法4
1.3 圖6
1.4 語言:基本概念7
問題與解答10
習題12
第2章 文法14
2.1 文法的定義和分類15
2.2 二義性24
2.3 CFG的化簡28
2.4 範式31
問題和解答36
習題39
第3章 有限狀態自動機44
3.1 確定有限狀態自動機(DFSA)45
3.2 不確定有限狀態自動機(NFSA)47
3.3 正則表達式51
問題與解答56
習題61
第4章 有限自動機:特徵、性質和可判定性65
4.1 有限自動機和正則文法65
4.2 正則集的泵浦引理66
4.3 封閉性68
4.4 可判定性定理70
問題和解答71
習題71
第5章 帶輸出的有限狀態自動機及其最小化73
5.1 Myhill鄄Nerode定理73
5.2 帶輸出的有限自動機77
問題與解答79
習題81
第6章 有限自動機的變形83
6.1 雙向有限自動機83
6.2 多頭有限狀態自動機88
6.3 機率有限自動機89
6.4 加權有限自動機和數字圖像92
問題與解答105
習題108
第7章 下推自動機110
7.1 下推自動機110
7.2 空棧接受和終態接受的等價113
7.3 CFG和PDA的等價114
問題與解答121
習題124
第8章 上下文無關文法性質與分析126
8.1 CFL的泵引理126
8.2 CFL的封閉性127
8.3 CFL的判定性質130
8.4 CFL的子群132
8.5 帕里克映射與帕里克定理134
8.6 自嵌入性138
8.7 同態下的特性139
問題與解答141
習題144
第9章 圖靈機147
9.1 作為接受器的圖靈機148
9.2 作為計算設備的圖靈機157
9.3 圖靈機的構造技術164
問題與解答168
習題172
第10章 圖靈機的變形175
10.1 通用版本175
10.2 受限圖靈機179
10.3 作為枚舉器的圖靈機181
10.4 圖靈機和0型語言的等價182
10.5 線性有界自動機183
10.6 歌德爾編號184
問題與解答185
習題187
第11章 通用圖靈機及可判定性189
11.1 圖靈機的編碼和枚舉189
11.2 遞歸和遞歸可枚舉集189
11.3 通用圖靈機192
11.4 問題,實例和語言195
11.5 萊斯定理195
11.6 規約問題以證明不可判定性197
11.7 波斯特對應問題198
11.8 可計算函式204
問題與解答208
習題209
第12章 時間與空間複雜度211
12.1 RAM模型211
12.2 圖靈機的時間與帶複雜度214
問題與解答228
習題232
第13章 最近的趨勢及套用233
13.1 正則重寫233
13.2 馬庫斯上下文文法241
13.3 林登麥伊爾系統248
13.4 文法系統及分散式自動機256
第14章 一些新的計算模型273
14.1 DNA計算273
14.2 膜計算282
單項選擇題(I)296
答案303
單項選擇題(II)304
答案311
參考文獻312
作者簡介
作者：(印度)卡馬拉(Kamala Krithivasan) (印度)拉瑪(Rama R) 譯者：孟宇龍 李健利 王宇華 合著者：馮曉寧
卡馬拉，Kamala Krithivasan，馬德拉斯大學博士，1975年進入印度理工學院馬德拉斯分校( IIMT)參加工作。計算機科學與工程學院教授，1992-1995年擔任院長，在IIMT有著30餘年的教學和研究經驗。她的研究方向包括形式語言理論、非傳統模型計算(如DNA計算)、膜計算以及離散分層計算等。Kamala教授是1986年福爾布萊特學術獎金的獲得者，同時還是印度國家工程學會的會員。
Rama R，1989年在安娜大學獲得博士學位。進入印度理工學院馬德拉斯分校(IIMT)擔任副教授之前，
曾在安娜大學工程學院任教。2006年晉職為教授並任教至今。Rama教授擁有20餘年的教學和研究經驗，並且指導過四位研究生的博士論文。她的研究領域是形式語言與自動機和自然計算。同時，她也是印度工業教育學會的終身會員。
