123,123

內(nèi)容簡(jiǎn)介

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

作者簡(jiǎn)介

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

圖書(shū)目錄

前言
第1章　語(yǔ)言及其表示
　1.1　字母表、串和語(yǔ)言
　　1.1.1　字母表
　　1.1.2　串
　　1.1.3　語(yǔ)言
　1.2　文法
　1.3　語(yǔ)言識(shí)別器
　習(xí)題1
第2章　正規(guī)表達(dá)式、正規(guī)文法與有限自動(dòng)機(jī)
　2.1　正規(guī)表達(dá)式與正規(guī)集
　2.2　正規(guī)文法和正規(guī)語(yǔ)言
　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ī)語(yǔ)言的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章　上下文無(wú)關(guān)文法與下推自動(dòng)機(jī)
　3.1　上下文無(wú)關(guān)文法
　3.2　推導(dǎo)樹(shù)
　　3.2.1　推導(dǎo)樹(shù)的定義和例子
　　3.2.2　推導(dǎo)樹(shù)與推導(dǎo)的關(guān)系
　　3.2.3　最左推導(dǎo)與最右推導(dǎo)
　　3.2.4　上下文無(wú)關(guān)文法的歧義性
　3.3　上下文無(wú)關(guān)文法的化簡(jiǎn)
　　3.3.1　無(wú)用字符
　　3.3.2　空產(chǎn)生式
　　3.3.3　單產(chǎn)生式
　3.4　喬姆斯基范式和格雷巴赫范式
　　3.4.1　喬姆斯基范式
　　3.4.2　格雷巴赫范式
　3.5　上下文無(wú)關(guān)語(yǔ)言的固有歧義性
　3.6　上下文無(wú)關(guān)文法的應(yīng)用
　　3.6.1　語(yǔ)法分析程序
　　3.6.2　語(yǔ)法分析程序生成器
　　3.6.3　超文本標(biāo)記語(yǔ)言
　　3.6.4　可擴(kuò)展標(biāo)記語(yǔ)言
　3.7　下推自動(dòng)機(jī)
　　3.7.1　下推自動(dòng)機(jī)的基本定義
　　3.7.2　兩種不同方式接受語(yǔ)言的下推自動(dòng)機(jī)的等價(jià)性
　　3.7.3　確定的下推自動(dòng)機(jī)
　3.8　上下文無(wú)關(guān)文法與下推自動(dòng)機(jī)的等價(jià)性
　3.9　上下文無(wú)關(guān)語(yǔ)言的Pumping引理
　習(xí)題3
第4章　圖靈機(jī)
第5章　喬姆斯基文法體系
第6章　語(yǔ)言的運(yùn)算與封閉性質(zhì)
第7章　判定問(wèn)題與不可判定性
第8章　確定的上下文無(wú)關(guān)語(yǔ)言
參考文獻(xiàn)