形式語言與自動機理論

內(nèi)容概要

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

作者簡介

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

書籍目錄

前言第1章　語言及其表示　1.1　字母表、串和語言　　1.1.1　字母表　　1.1.2　串　　1.1.3　語言　1.2　文法　1.3　語言識別器　習(xí)題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　帶ε-轉(zhuǎn)換的不確定有限自動機　2.4　正規(guī)表達式、正規(guī)文法與有限自動機的等價性　　2.4.1　正規(guī)表達式與有限自動機的等價性　　2.4.2　正規(guī)文法與有限自動機的等價性　　2.4.3　把正規(guī)文法和有限自動機轉(zhuǎn)化為正規(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ī)表達式和有限自動機的應(yīng)用　　2.8.1　詞法分析程序　　2.8.2　文本編輯程序　　2.8.3　文本搜索與字符串匹配　　2.8.4　時序電路的分析與設(shè)計　習(xí)題2第3章　上下文無關(guān)文法與下推自動機　3.1　上下文無關(guān)文法　3.2　推導(dǎo)樹　　3.2.1　推導(dǎo)樹的定義和例子　　3.2.2　推導(dǎo)樹與推導(dǎo)的關(guān)系　　3.2.3　最左推導(dǎo)與最右推導(dǎo)　　3.2.4　上下文無關(guān)文法的歧義性　3.3　上下文無關(guān)文法的化簡　　3.3.1　無用字符　　3.3.2　空產(chǎn)生式　　3.3.3　單產(chǎn)生式　3.4　喬姆斯基范式和格雷巴赫范式　　3.4.1　喬姆斯基范式　　3.4.2　格雷巴赫范式　3.5　上下文無關(guān)語言的固有歧義性　3.6　上下文無關(guān)文法的應(yīng)用　　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　上下文無關(guān)文法與下推自動機的等價性　3.9　上下文無關(guān)語言的Pumping引理　習(xí)題3第4章　圖靈機第5章　喬姆斯基文法體系第6章　語言的運算與封閉性質(zhì)第7章　判定問題與不可判定性第8章　確定的上下文無關(guān)語言參考文獻

圖書封面

評論、評分、閱讀與下載

---

    形式語言與自動機理論 PDF格式下載

---