形式語言與自動機理論（第3版）

內容簡介

本書是作者結合其近30年來在大學講授該門課程的經驗和體會，選擇和組織有關內容撰寫而成。基於計算機問題求解的需要討論正則語言、上下文無關語言的文法、識別模型及其性質、圖靈機的基本知識。其內容特點是抽象和形式化，既有嚴格的理論證明，又具有很強的構造性。敘述中特別注意引導讀者分析與解決問題，以培養學生的形式化描述和抽象思維能力，使學生了解和初步掌握“問題、形式化、自動化（計算機化）”的解題思路。為了便於學生對內容的掌握，附錄A還給出了建議的教學設計。本書配套出版有《形式語言與自動機理論教學參考書（第3版）》，歸納各章知識點，解讀主要內容，解析典型習題。

形式語言與自動機理論是計算機科學與技術專業的一門重要課程。本書是作者結合其近30年來在大學講授該門課程的經驗和體會，選擇和組織有關內容撰寫而成。基於計算機問題求解的需要討論正則語言、上下文無關語言的文法、識別模型及其性質、圖靈機的基本知識。其內容特點是抽象和形式化，既有嚴格的理論證明，又具有很強的構造性。敘述中特別注意引導讀者分析與解決問題，以培養學生的形式化描述和抽象思維能力，使學生了解和初步掌握“問題、形式化、自動化（計算機化）”的解題思路。為了便於學生對內容的掌握，附錄A還給出了建議的教學設計。本書配套出版有《形式語言與自動機理論教學參考書（第3版）》，歸納各章知識點，解讀主要內容，解析典型習題。

圖書目錄

第1章緒論11.1集合的基礎知識2

1.1.1集合及其表示2

1.1.2集合之間的關係4

1.1.3集合的運算5

1.2關係10

1.2.1二元關係10

1.2.2等價關係與等價類11

1.2.3關係的合成12

1.2.4遞歸定義與歸納證明12

1.2.5關係的閉包15

1.3圖15

1.3.1無向圖16

1.3.2有向圖17

1.3.3樹19

1.4語言20

1.4.1什麼是語言20

1.4.2形式語言與自動機理論的產生與作用21

1.4.3基本概念23

1.5小結28

習題29

第2章文法35

2.1啟示36

2.2形式定義38

2.3文法的構造46

2.4文法的喬姆斯基體系54

2.5空語句64

2.6小結66

習題66目錄形式語言與自動機理論(第3版)第3章有窮狀態自動機70

3.1語言的識別70

3.2有窮狀態自動機72

3.3不確定的有窮狀態自動機83

3.3.1作為對DFA的修改83

3.3.2NFA的形式定義84

3.3.3NFA與DFA等價86

3.4帶空移動的有窮狀態自動機90

形式語言與自動機理論（第3版）

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條