形式語言與自動機

定　價：￥16.00

作　者：	王柏，楊娟編著
出版社：	北京郵電大學出版社
叢編項：	21世紀計算機科學與技術系列教材
標　簽：	自動機

購買這本書可以去

ISBN：	9787563506699	出版時間：	2003-05-30	包裝：	平裝
開本：	21cm	頁數(shù)：	288	字數(shù)：

內(nèi)容簡介

　　本書扼要地介紹了形式語言與自動機的基本體系，是學習理論計算機科學基礎的教材和參考書。書中主要介紹了形式語言的基本概念、自動機的模型以及形式語言與自動機的等價性，包括右線性文法與有限自動機、上下文無關文法與下推自動機、圖靈機以及無限制文法等。同時介紹了自動機在通信領域的某些應用。本書不追求過多形式化討論，強調(diào)基本概念的直觀背景和主要定理證明的思路分析。書中配有較多的例題和習題，可作為工科計算機專業(yè)本科生的教材和研究人員的參考書。

作者簡介

暫缺《形式語言與自動機》作者簡介

圖書目錄

第1章  基礎知識
1. 1  集合與關系
1. 2  邏輯
1. 3  圖
1. 4  證明技術
1, 4. 1  演繹證明
1. 4. 2  反證法
1. 4. 3  歸納定義與歸納法
習題

第2章  語言及文法
2. 1  語言的定義與運算
2. 2  文法
2. 3  文法的分類
習題

第3章  有限自動機和右線性文法
3. 1  有限自動機
3. 1. 1  有限狀態(tài)系統(tǒng)和有限自動機的概念
3. 1. 2  有限自動機的形式定義
3. 1. 3  設計有限自動機
3. 2  不確定的有限自動機
3. 3  DFA與NFA的等效
3. 4  有c轉(zhuǎn)換的不確定的有限自動機
3. 5  正則集與正則式
3. 6  右線性文法和正則集
3. 7  正則表達式和有限自動機
3. 8  右線性語言與有限自動機
3. 9  右線性語言的性質(zhì)
3. 9. 1  確定的有限自動機的化簡
3. 9. 2  泵浦引理
3. 9. 3  右線性語言的封閉性
3. 9. 4  判定問題
3. 10  雙向和有輸出的有限自動機
3. 10. 1  雙向有限自動機
3. 10. 2  有輸出的有限自動機
習題

第4章  上下文無關文法與下推自動機
4. 1  推導樹與二義性
4. 2  上下文無關文法的變換
4. 3  Chomsky范式和Greibach范式
4. 4  下推自動機
4. 5  上下文無關文法與下推自動機
4. 6  上下文無關語言的性質(zhì)
4. 6. 1  關于上下文無關語言的泵浦引理
4. 6. 2  上下文無關語言的封閉性
4. 6. 3  上下文無關語言的判定問題
4. 6. 4  二義性
4. 7  受限型上下文無關文法
習題

第5章  圖靈機
5. 1  基本圖靈機
5. 2  圖靈機的構造技術
5. 2. 1  控制器的存儲
5. 2. 2  多道機
5. 2. 3  核對符
5. 2. 4  移位
5. 2. 5  子程序
5. 3  修改型圖靈機
5. 3. 1  雙向無限帶圖靈機
5. 3. 2  多帶圖靈機
5. 3. 3  不確定的圖靈機
5. 3. 4  二維圖靈機
5. 4  圖靈機與無限制文法
5. 5  線性有界自動機與上下文有關文法
習題

第6章  翻譯
6. 1  翻譯式
6. 2  轉(zhuǎn)換器
6. 2. 1有限轉(zhuǎn)換器
6. 2. 2下推轉(zhuǎn)換器
6. 3  詞法分析
6. 4  句法分析
6. 4. 1  自上而下解析
6. 4. 2  自下而上解析
習題

第7章  自動機理論在通信領域的應用
7. 1  狀態(tài)機基本模型及其局限性
7. 2  MSC和SDL簡介
7. 3  應用狀態(tài)機模型描述協(xié)議
附錄  計算復雜性與可計算性基礎
參考文獻