形式語言與自動(dòng)機(jī)理論

內(nèi)容概要

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

作者簡(jiǎn)介

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

書籍目錄

前言第1章　語言及其表示　1.1　字母表、串和語言　　1.1.1　字母表　　1.1.2　串　　1.1.3　語言　1.2　文法　1.3　語言識(shí)別器　習(xí)題1第2章　正規(guī)表達(dá)式、正規(guī)文法與有限自動(dòng)機(jī)　2.1　正規(guī)表達(dá)式與正規(guī)集　2.2　正規(guī)文法和正規(guī)語言　2.3　有限自動(dòng)機(jī)　　2.3.1　有限狀態(tài)系統(tǒng)　　2.3.2　確定的有限自動(dòng)機(jī)　　2.3.3　不確定的有限自動(dòng)機(jī)　　2.3.4　帶ε-轉(zhuǎn)換的不確定有限自動(dòng)機(jī)　2.4　正規(guī)表達(dá)式、正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性　　2.4.1　正規(guī)表達(dá)式與有限自動(dòng)機(jī)的等價(jià)性　　2.4.2　正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性　　2.4.3　把正規(guī)文法和有限自動(dòng)機(jī)轉(zhuǎn)化為正規(guī)表達(dá)式方程組求解　2.5　正規(guī)語言的Pumping引理　2.6　帶輸出的有限自動(dòng)機(jī)　　2.6.1　Moore機(jī)　　2.6.2　Mea1y機(jī)　　2.6.3　Moore機(jī)同Mea1y機(jī)的等價(jià)性　2.7　有限自動(dòng)機(jī)的化簡(jiǎn)　　2.7.1　米希爾-尼羅德定理　　2.7.2　最簡(jiǎn)有限自動(dòng)機(jī)　　2.7.3　有限自動(dòng)機(jī)的化簡(jiǎn)方法　2.8　正規(guī)表達(dá)式和有限自動(dòng)機(jī)的應(yīng)用　　2.8.1　詞法分析程序　　2.8.2　文本編輯程序　　2.8.3　文本搜索與字符串匹配　　2.8.4　時(shí)序電路的分析與設(shè)計(jì)　習(xí)題2第3章　上下文無關(guān)文法與下推自動(dòng)機(jī)　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)文法的化簡(jiǎ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　超文本標(biāo)記語言　　3.6.4　可擴(kuò)展標(biāo)記語言　3.7　下推自動(dòng)機(jī)　　3.7.1　下推自動(dòng)機(jī)的基本定義　　3.7.2　兩種不同方式接受語言的下推自動(dòng)機(jī)的等價(jià)性　　3.7.3　確定的下推自動(dòng)機(jī)　3.8　上下文無關(guān)文法與下推自動(dòng)機(jī)的等價(jià)性　3.9　上下文無關(guān)語言的Pumping引理　習(xí)題3第4章　圖靈機(jī)第5章　喬姆斯基文法體系第6章　語言的運(yùn)算與封閉性質(zhì)第7章　判定問題與不可判定性第8章　確定的上下文無關(guān)語言參考文獻(xiàn)

圖書封面

評(píng)論、評(píng)分、閱讀與下載

---

    形式語言與自動(dòng)機(jī)理論 PDF格式下載

---