形式語言與自動機

本書採用通俗的語言和形象化的方法來表達概念和定理，邏輯嚴謹、思維縝密，可作為高等院校計算機及相關專業“形式語言與自動機”課程的教材。

陳有祺，南開大學信息技術科學學院教授，多年來一直從事計算機軟體方面的教學和研究工作，從1993年起享受國務院政府特殊津貼。講授的課程主要有程序設計語言．編譯原理，數據結構、形式語言與自動機等，研究領域包括編譯理論、人工智慧、自然語言理解，形式語言等。1980年至1982年在美國西密歇根大學作訪問學者，研修人工智慧和形式語言，回國后一直為研究生講授“形式語言與自動機”課程。相關著作包括：《BCLR（k）文法及其分析演演算法》、《廣義上下文無關文法和它的語法分析》、《從輸入輸出序列確定自動機的結構》，《形式語言與自動機》等。

本書以四類形式語言（短語結構語言，上下文有關語言。上下文無關語言。正則語言）和四種自動機（有窮自動機、下推自動機．圖靈機，線性有界自動機）為主線，討論了形式語言與自動機方面的主要理論成果和應用實例。

本書的主要特色：

取材豐富。涵蓋了該領域國內外現有教材的主要內容。

在寫作方法上，循序漸進，深入淺出。在概念的引入和定理的證明上，盡量採用通俗的語言和形象化的方法來表達。

理論與實際相結合。除具有配合定理和定義的大量例題外，許多章節還有現代計算機技術中應用的實例。

適應面廣。既適合作為本科生的教材，也適合作為研究生的教材。

出版者的話

序言

前言

教學建議

第1章　預備知識

1.1　定理及其證明方法

1.1.1　演繹法

1.1.2　反證法

1.1.3　歸納法

1.2　集合及其基本運算

1.2.1　集合基礎知識

1.2.2　集合的基本運算

1.2.3　關係與映射

1.3　圖和樹簡介

1.3.1圖的基本概念

1.3.2圖的矩陣表示

1.3.3　樹的基本知識

1.4　字母表、字元串和語言

習題

第2章　文法的一般理論

2.1　問題的提出

2.2　形式文法與形式語言

2.3　文法的喬姆斯基分類

習題

第3章　有窮自動機

3.1　非形式化描述

3.2　有窮自動機的基本定義

3.3　非確定的有窮自動機

3.4　具有￡轉移的有窮自動機

3.5　有窮自動機的應用

3.5.1　在文本中查找字元串

3.5.2　用於文本搜索的非確定的有窮自動機

3.5.3　識別關鍵字集合的DFA

3.6　具有輸出的有窮自動機

習題

第4章　正則表達式

4.1　正則表達式的定義

4.2　正則表達式和有窮自動機的關係

4.3則表達式的等價變換

4.3.1　交換律與結合律

4.3.2　單位元與零元

4.3.3　分配律

4.3.4　與“*”構造有關的定律

4.3.5　發現正則表達式定律的一般方法

4.4　正則表達式的應用

4.4.1UNIX中的正則表達式

4.4.2　詞法分析

4.4.3　查找文本中的模式

習題

第5章正則語言的性質

5.1　正則文法和有窮自動機的關係

5.2　正則語言的泵引理

5.3　正則語言的封閉性

5.4　正則語言的判定演演算法

5.5　有窮自動機的最小化

習題

第6章　上下文無關文法

6.1上下文無關文法的語法分析

6.2　上下文無關文法的化簡

6.3　上下文無關文法的範式

6.4　上下文無關文法的應用

6.4.1　用上下文無關文法描述語言

6.4.2　語法分析器生成工具YACC

……

第7章　下推自動機

第8章　上下文無關語言的性質

第9章　圖靈機導引

第10章　不可判定性

第11章　線性有界自動機和上下文有關文法

第12章　確定的上下文無關語言和LR（k）文法

參考文獻

……