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

內(nèi)容概要

　　形式語(yǔ)言與自動(dòng)機(jī)理論是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的一門(mén)重要課程。本書(shū)是作者結(jié)合其20余年來(lái)在大學(xué)講授該門(mén)課程的經(jīng)驗(yàn)和體會(huì)，選擇和組織有關(guān)內(nèi)容撰寫(xiě)而成。不僅含有有關(guān)正則語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言的文法、識(shí)別模型及其性質(zhì)、圖靈機(jī)的基本知識(shí)，更涉及到本學(xué)科方法論中所包含的3個(gè)學(xué)科形態(tài)。其內(nèi)容特點(diǎn)是抽象和形式化，既有嚴(yán)格的理論證明，又具有很強(qiáng)的構(gòu)造性，從而培養(yǎng)學(xué)生的形式化描述和抽象思維能力，使學(xué)生了解和初步掌握“問(wèn)題、形式化、自動(dòng)化(計(jì)算機(jī)化)”的解題思路。為了便于學(xué)生對(duì)內(nèi)容的掌握，附錄A還給出了建議的教學(xué)設(shè)計(jì)?！　　?br />　　本書(shū)配套出版有《形式語(yǔ)言與自動(dòng)機(jī)理論教學(xué)參考書(shū)(第2版)》，歸納各章知識(shí)點(diǎn)，解讀主要內(nèi)容，解析典型習(xí)題?！　　?br />　　本書(shū)適合作為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的高年級(jí)本科生、研究生的教材，也可供相關(guān)專(zhuān)業(yè)的學(xué)生、教師和科研人員參考。

作者簡(jiǎn)介

蔣宗禮，1978年3月至1984年7月在哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)科學(xué)習(xí)，先后到美國(guó)、加拿大進(jìn)修，在哈爾濱工業(yè)大學(xué)和北京工業(yè)大學(xué)主講編譯原理、形式語(yǔ)言與自動(dòng)機(jī)理論、人工神經(jīng)網(wǎng)絡(luò)等課程。國(guó)家級(jí)教學(xué)名師，國(guó)家級(jí)教學(xué)團(tuán)隊(duì)負(fù)責(zé)人，國(guó)家精品課程負(fù)責(zé)人，主編有國(guó)家級(jí)精品教材，獲國(guó)家教學(xué)成果二等獎(jiǎng)2項(xiàng)，另有十余項(xiàng)省部級(jí)教學(xué)、科研成果一、二、三等獎(jiǎng)。曾獲中國(guó)高校優(yōu)秀青年學(xué)者、寶鋼優(yōu)秀教師、航天部?jī)?yōu)秀青年教師等榮譽(yù)稱(chēng)號(hào)。主要學(xué)術(shù)兼職有中國(guó)工程教育認(rèn)證協(xié)會(huì)籌備委員會(huì)學(xué)術(shù)委員會(huì)委員、中國(guó)工程教育認(rèn)證協(xié)會(huì)籌備委員會(huì)2012-2013年度結(jié)論審議委員會(huì)委員、全國(guó)工程教育專(zhuān)業(yè)認(rèn)證專(zhuān)家委員會(huì)計(jì)算機(jī)類(lèi)專(zhuān)業(yè)認(rèn)證分委員會(huì)成員、教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)教學(xué)指導(dǎo)分委員會(huì)秘書(shū)長(zhǎng)、全國(guó)高校計(jì)算機(jī)教育研究會(huì)理事長(zhǎng)、中國(guó)計(jì)算機(jī)學(xué)會(huì)教育專(zhuān)業(yè)委員會(huì)副主任。

書(shū)籍目錄

第1章 緒論
1.1 集合的基礎(chǔ)知識(shí)
1.1.1 集合及其表示
1.1.2 集合之間的關(guān)系
1.1.3 集合的運(yùn)算
1.2 關(guān)系
1.2.1 二元關(guān)系
1.2.2 等價(jià)關(guān)系與等價(jià)類(lèi)
1.2.3 關(guān)系的合成
1.2.4 遞歸定義與歸納證明
1.2.5 關(guān)系的閉包
1.3 圖19
1.3.1 無(wú)向圖
1.3.2 有向圖
1.3.3 樹(shù)
1.4 語(yǔ)言
1.4.1 什么是語(yǔ)言
1.4.2 形式語(yǔ)言與自動(dòng)機(jī)理論的產(chǎn)生與作用
1.4.3 基本概念
1.5 小結(jié)
習(xí)題
第2章 文法
2.1 啟示
2.2 形式定義
2.3 文法的構(gòu)造
2.4 文法的喬姆斯基體系
2.5 空語(yǔ)句
2.6 小結(jié)
習(xí)題82
第3章 有窮狀態(tài)自動(dòng)機(jī)
3.1 語(yǔ)言的識(shí)別
3.2 有窮狀態(tài)自動(dòng)機(jī)
3.3 不確定的有窮狀態(tài)自動(dòng)機(jī)
3.3.1 作為對(duì)DFA的修改
3.3.2 NFA的形式定義
3.3.3 NFA與DFA等價(jià)
3.4 帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)
3.5 FA是正則語(yǔ)言的識(shí)別器
3.5.1 FA與右線(xiàn)性文法
3.5.2 FA與左線(xiàn)性文法
3.6 FA的一些變形
3.6.1 雙向有窮狀態(tài)自動(dòng)機(jī)
3.6.2 帶輸出的FA
3.7 小結(jié)
習(xí)題
第4章 正則表達(dá)式
4.1 啟示
4.2 正則表達(dá)式的形式定義
4.3 正則表達(dá)式與FA等價(jià)
4.3.1 正則表達(dá)式到FA的等價(jià)變換
4.3.2 正則語(yǔ)言可以用正則表達(dá)式表示
4.4 正則語(yǔ)言等價(jià)模型的總結(jié)
4.5 小結(jié)
習(xí)題153
第5章 正則語(yǔ)言的性質(zhì)
5.1 正則語(yǔ)言的泵引理
……
第6章 上下文無(wú)關(guān)語(yǔ)言
第7章 下推自動(dòng)機(jī)
第8章 上下文無(wú)關(guān)語(yǔ)言的性質(zhì)
第9章 圖靈機(jī)
第10章 上下文有關(guān)語(yǔ)言
附錄A 教學(xué)設(shè)計(jì)
附錄B 縮寫(xiě)符號(hào)
詞匯索引
參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   9.2.4 多維圖靈機(jī) 前面介紹過(guò)的圖靈機(jī)的帶都是一維的。也就是說(shuō)，那些圖靈機(jī)的輸入帶要么是只可以向右無(wú)限延長(zhǎng)的，要么是只可以向左和向右延長(zhǎng)的，因而讀頭只能向前或者向后移動(dòng)?，F(xiàn)在將圖靈機(jī)的帶定義成多維的。這種圖靈機(jī)的讀頭可以沿著多個(gè)維移動(dòng)，稱(chēng)這種圖靈機(jī)為多維圖靈機(jī)（multi-dimensional Turing machine）。如果一個(gè)圖靈機(jī)可以沿著k維移動(dòng)，則稱(chēng)之為k維圖靈機(jī)（k-dimensional Turing machine）。k維圖靈機(jī)的帶由志維陣列組成，而且在所有的2k個(gè)方向上都是無(wú)窮的，它的讀頭可以向著2k個(gè)方向中的任一個(gè)移動(dòng)。對(duì)前面曾經(jīng)討論過(guò)的雙向無(wú)窮帶圖靈機(jī)來(lái)說(shuō)，雖然它的帶在左、右兩個(gè)方向上都是無(wú)窮，但是，在圖靈機(jī)的運(yùn)行期間的任意時(shí)刻，只有有限長(zhǎng)度的帶上含有非空白的內(nèi)容。與此相同，在任意時(shí)刻，一個(gè)k維圖靈機(jī)的每一維上也只有有限多個(gè)道各自含有有窮多個(gè)非空白字符。這就是說(shuō)，這些非空白的內(nèi)容可以被一個(gè)有限的k維立方體所包含。這使得我們可以將這k個(gè)維上的有窮長(zhǎng)度的字符串用適當(dāng)?shù)姆绞浇M合成可以在一維帶上存放的字符串。這種做法與我們?cè)谟?jì)算機(jī)中存放多維數(shù)組的做法一樣。 為了說(shuō)明具體的做法，下面討論二維圖靈機(jī)如何被一維圖靈機(jī)模擬。只要找到了相應(yīng)的模擬方法，按照“遞歸定義”、“遞歸求解”的思路，很容易得到志維圖靈機(jī)到一維圖靈機(jī)的轉(zhuǎn)換方法。 設(shè)M是一個(gè)二維圖靈機(jī)，按照“行優(yōu)先”的方式用一維帶來(lái)存放它的內(nèi)容。圖9-10是M在某一時(shí)刻帶上的所有非空白字符的存儲(chǔ)情況，可以用一個(gè)符串表示這一內(nèi)容。它正好對(duì)應(yīng)于一維帶的表示。我們約定，每行的內(nèi)容之間用一個(gè)特殊的帶符號(hào)#相隔。稱(chēng)一行的內(nèi)容為一段（segment），并且將#稱(chēng)為段分割符?！橛米髟撟址拈_(kāi)始標(biāo)志，＄用作該字符串的結(jié)束標(biāo)志。這樣，圖9-10所示的帶內(nèi)容可以用如下字符串表示： ￠Ba1a1a3a4BBBBBB#Ba5Ba6a7a8a9a10 BBB#Ba11 BBBBa12 Ba13 Ba14#a15a16 BBBBBBBBa16 # BBBa17 BBBBBa18 B#a19a20 BBBBBBBBB#BBBBBBBBBBa21＄ 現(xiàn)在來(lái)具體考慮一維圖靈機(jī)M′如何實(shí)現(xiàn)對(duì)二維圖靈機(jī)M的移動(dòng)的模擬。

編輯推薦

《普通高等教育"十一五"國(guó)家級(jí)規(guī)劃教材?21世紀(jì)大學(xué)本科計(jì)算機(jī)專(zhuān)業(yè)系列教材:形式語(yǔ)言與自動(dòng)機(jī)理論(第2版)》強(qiáng)調(diào)能力培養(yǎng)，以知識(shí)為載體，注重模型建立、構(gòu)造、變換、證明的方法與思想探討，引導(dǎo)讀者挖掘知識(shí)背后的內(nèi)容，強(qiáng)化專(zhuān)業(yè)基本能力和創(chuàng)新能力的培養(yǎng)。取材合適，結(jié)構(gòu)嚴(yán)謹(jǐn)，深入淺出，把握知識(shí)點(diǎn)間的聯(lián)系，安排鋪墊，分散難點(diǎn)，突出重點(diǎn)，努力化解深?yuàn)W，保持基本內(nèi)容抽象和形式化，通過(guò)思路表達(dá)的可視化提高了易懂性，富有啟發(fā)性，使抽象、枯燥的內(nèi)容變得吸引人。《普通高等教育"十一五"國(guó)家級(jí)規(guī)劃教材?21世紀(jì)大學(xué)本科計(jì)算機(jī)專(zhuān)業(yè)系列教材:形式語(yǔ)言與自動(dòng)機(jī)理論(第2版)》適合作為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的高年級(jí)本科生、研究生的教材，也可供相關(guān)專(zhuān)業(yè)的學(xué)生、教師和科研人員參考。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

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

---

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

---