形式語言與自動機理論

定　價：￥20.00

作　者：	吳哲輝、吳振寰
出版社：	機械工業(yè)出版社
叢編項：
標　簽：	方法

購買這本書可以去

ISBN：	9787111209980	出版時間：	2007-04-01	包裝：	平裝
開本：	16	頁數(shù)：	180	字數(shù)：

內(nèi)容簡介

　　形式語言與自動機理論是計算機科學理論的重要基礎。本書主要介紹喬姆斯基文法體系的四類文法以及它們與有限自動機、下推自動機、線性界限自動機和圖靈機之間的關系。此外，對語言的各種運算和封閉性質、判定問題及不可判定性以及確定的上下文無關語言與LR-文法也進行了討論。書中還介紹了一些文法和自動機在文本編輯、編譯程序、標注語言以及邏輯電路和時序電路設計中的應用?！缎问秸Z言與自動機理論》共分8章：第1章介紹語言及其表示；第2章介紹正規(guī)表達式、正規(guī)文法與有限自動機；第3章介紹上下文無關文法與下推自動機；第4章介紹圖靈機；第5章介紹喬姆斯基文法體系；第6章介紹語言的運算與封閉性質；第7章介紹判定問題與不可判定性；第8章介紹確定的上下文無關語言和LR-文法?！缎问秸Z言與自動機理論》可作為高等學校計算機及相關專業(yè)研究生及高年級本科生課程教材，也可供從事計算機研究和開發(fā)的技術人員參考。為方便教師教學，本書配有教學課件，歡迎選用本書作為教材的老師索取，索取郵箱：llm7785@sina.com。

作者簡介

　　吳哲輝，1941年3月生于廣東省連州市，1965年畢業(yè)于中山大學數(shù)學力學系。1981年到1983年在美國芝加哥伊利諾伊大學作訪問學者，學習計算機科學理論，從那時起開始從事Petri網(wǎng)理論及應用的研究工作?，F(xiàn)任山東科技大學教授、博士生導師，中國計算機學會Petri網(wǎng)專委會主任。

圖書目錄

前言
第1章　語言及其表示
　1.1　字母表、串和語言
　　1.1.1　字母表
　　1.1.2　串
　　1.1.3　語言
　1.2　文法
　1.3　語言識別器
　習題1
第2章　正規(guī)表達式、正規(guī)文法與有限自動機
　2.1　正規(guī)表達式與正規(guī)集
　2.2　正規(guī)文法和正規(guī)語言
　2.3　有限自動機
　　2.3.1　有限狀態(tài)系統(tǒng)
　　2.3.2　確定的有限自動機
　　2.3.3　不確定的有限自動機
　　2.3.4　帶ε-轉換的不確定有限自動機
　2.4　正規(guī)表達式、正規(guī)文法與有限自動機的等價性
　　2.4.1　正規(guī)表達式與有限自動機的等價性
　　2.4.2　正規(guī)文法與有限自動機的等價性
　　2.4.3　把正規(guī)文法和有限自動機轉化為正規(guī)表達式方程組求解
　2.5　正規(guī)語言的Pumping引理
　2.6　帶輸出的有限自動機
　　2.6.1　Moore機
　　2.6.2　Mea1y機
　　2.6.3　Moore機同Mea1y機的等價性
　2.7　有限自動機的化簡
　　2.7.1　米希爾-尼羅德定理
　　2.7.2　最簡有限自動機
　　2.7.3　有限自動機的化簡方法
　2.8　正規(guī)表達式和有限自動機的應用
　　2.8.1　詞法分析程序
　　2.8.2　文本編輯程序
　　2.8.3　文本搜索與字符串匹配
　　2.8.4　時序電路的分析與設計
　習題2
第3章　上下文無關文法與下推自動機
　3.1　上下文無關文法
　3.2　推導樹
　　3.2.1　推導樹的定義和例子
　　3.2.2　推導樹與推導的關系
　　3.2.3　最左推導與最右推導
　　3.2.4　上下文無關文法的歧義性
　3.3　上下文無關文法的化簡
　　3.3.1　無用字符
　　3.3.2　空產(chǎn)生式
　　3.3.3　單產(chǎn)生式
　3.4　喬姆斯基范式和格雷巴赫范式
　　3.4.1　喬姆斯基范式
　　3.4.2　格雷巴赫范式
　3.5　上下文無關語言的固有歧義性
　3.6　上下文無關文法的應用
　　3.6.1　語法分析程序
　　3.6.2　語法分析程序生成器
　　3.6.3　超文本標記語言
　　3.6.4　可擴展標記語言
　3.7　下推自動機
　　3.7.1　下推自動機的基本定義
　　3.7.2　兩種不同方式接受語言的下推自動機的等價性
　　3.7.3　確定的下推自動機
　3.8　上下文無關文法與下推自動機的等價性
　3.9　上下文無關語言的Pumping引理
　習題3
第4章　圖靈機
第5章　喬姆斯基文法體系
第6章　語言的運算與封閉性質
第7章　判定問題與不可判定性
第8章　確定的上下文無關語言
參考文獻