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

內(nèi)容概要

本書以四類形式語言（短語結(jié)構(gòu)語言、上下文有關(guān)語言、上下文無關(guān)語言、正則語言）和四種自動(dòng)機(jī)（有窮自動(dòng)機(jī)、下推自動(dòng)機(jī)、圖靈機(jī)、線性有界自動(dòng)機(jī)）為主線，討論了形式語言與自動(dòng)機(jī)方面的主要理論成果和應(yīng)用實(shí)例。書中每一章的最后都配有大量不同難度的習(xí)題，有助于讀者掌握本書內(nèi)容。        本書采用通俗的語言和形象化的方法來表達(dá)概念和定理，邏輯嚴(yán)謹(jǐn)、思維縝密，可作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)“形式語言與自動(dòng)機(jī)”課程的教材。

作者簡(jiǎn)介

陳有祺，南開大學(xué)信息技術(shù)科學(xué)學(xué)院教授，多年來一直從事計(jì)算機(jī)軟件方面的教學(xué)和研究工作，從1993年起享受國(guó)務(wù)院政府特殊津貼。講授的課程主要有程序設(shè)計(jì)語言．編譯原理，數(shù)據(jù)結(jié)構(gòu)、形式語言與自動(dòng)機(jī)等，研究領(lǐng)域包括編譯理論、人工智能、自然語言理解，形式語言等。1980年至1

書籍目錄

出版者的話序言前言教學(xué)建議第1章　預(yù)備知識(shí)　1.1　定理及其證明方法　　1.1.1　演繹法　　1.1.2　反證法　　1.1.3　歸納法　1.2　集合及其基本運(yùn)算　　1.2.1　集合基礎(chǔ)知識(shí)　　1.2.2　集合的基本運(yùn)算　　1.2.3　關(guān)系與映射　1.3　圖和樹簡(jiǎn)介　　1.3.1  圖的基本概念　　1.3.2  圖的矩陣表示　　1.3.3　樹的基本知識(shí)　1.4　字母表、字符串和語言　習(xí)題第2章　文法的一般理論　2.1　問題的提出　2.2　形式文法與形式語言　2.3　文法的喬姆斯基分類　習(xí)題第3章　有窮自動(dòng)機(jī)　3.1　非形式化描述　3.2　有窮自動(dòng)機(jī)的基本定義　3.3　非確定的有窮自動(dòng)機(jī)　3.4　具有￡轉(zhuǎn)移的有窮自動(dòng)機(jī)　3.5　有窮自動(dòng)機(jī)的應(yīng)用　　3.5.1　在文本中查找字符串　　3.5.2　用于文本搜索的非確定的有窮自動(dòng)機(jī)　　3.5.3　識(shí)別關(guān)鍵字集合的DFA  3.6　具有輸出的有窮自動(dòng)機(jī)  習(xí)題第4章　正則表達(dá)式  4.1　正則表達(dá)式的定義  4.2　正則表達(dá)式和有窮自動(dòng)機(jī)的關(guān)系  4.3  則表達(dá)式的等價(jià)變換　　4.3.1　交換律與結(jié)合律　　4.3.2　單位元與零元　　4.3.3　分配律　　4.3.4　與“*”構(gòu)造有關(guān)的定律　　4.3.5　發(fā)現(xiàn)正則表達(dá)式定律的一般方法  4.4　正則表達(dá)式的應(yīng)用　　4.4.1  UNIX中的正則表達(dá)式　　4.4.2　詞法分析　　4.4.3　查找文本中的模式  習(xí)題第5章  正則語言的性質(zhì)  5.1　正則文法和有窮自動(dòng)機(jī)的關(guān)系  5.2　正則語言的泵引理  5.3　正則語言的封閉性  5.4　正則語言的判定算法  5.5　有窮自動(dòng)機(jī)的最小化  習(xí)題第6章　上下文無關(guān)文法  6.1  上下文無關(guān)文法的語法分析  6.2　上下文無關(guān)文法的化簡(jiǎn)  6.3　上下文無關(guān)文法的范式  6.4　上下文無關(guān)文法的應(yīng)用　　6.4.1　用上下文無關(guān)文法描述語言　　6.4.2　語法分析器生成工具YACC　　……第7章　下推自動(dòng)機(jī)第8章　上下文無關(guān)語言的性質(zhì)　第9章　圖靈機(jī)導(dǎo)引第10章　不可判定性第11章　線性有界自動(dòng)機(jī)和上下文有關(guān)文法第12章　確定的上下文無關(guān)語言和LR（k）文法參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁：第3章 有窮自動(dòng)機(jī)繼文法的一般理論之后，本章引入語言的另一種表示形式——有窮自動(dòng)機(jī)。雖然有窮自動(dòng)機(jī)是所有自動(dòng)機(jī)中最簡(jiǎn)單的一種，它表示語言的能力是有限的，但是它構(gòu)造簡(jiǎn)單，在生產(chǎn)和生活中都有它的原型，因此它在計(jì)算機(jī)科學(xué)技術(shù)和其他學(xué)科中都有廣泛的應(yīng)用。掌握了有窮自動(dòng)機(jī)的基本概念，將為后面學(xué)習(xí)其他更復(fù)雜的自動(dòng)機(jī)打下良好的基礎(chǔ)。3.1 非形式化描述在客觀世界中，具有有窮多個(gè)狀態(tài)的系統(tǒng)比比皆是。例如，日常用的指針式鐘表就是一種有窮狀態(tài)系統(tǒng)，它共有12×60×60個(gè)狀態(tài)，秒針每走一步，系統(tǒng)就從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)。一局棋也是一種有窮狀態(tài)系統(tǒng)，如圍棋共有3（361）個(gè)狀態(tài)，棋手每走一步，就從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)。在工業(yè)產(chǎn)品中，也有很多類似的例子。比如，電梯的控制結(jié)構(gòu)就是有窮狀態(tài)系統(tǒng)的一個(gè)典型例子。電梯停在每一樓層作為一個(gè)狀態(tài)，它的控制系統(tǒng)不必記住以前的所有動(dòng)作，而只要知道現(xiàn)在的位置以及用戶給出的信號(hào)就可以通過改變它的狀態(tài)（上或下）來滿足用戶的要求。某些電子產(chǎn)品中的開關(guān)電路，是有窮狀態(tài)系統(tǒng)的又一實(shí)際例子。一個(gè)開關(guān)電路由有窮多個(gè)門電路組成，每個(gè)“門”可以處于兩種狀態(tài)——開和關(guān)（通常記為1和0）之一。具有n個(gè)門的開關(guān)網(wǎng)絡(luò)有2（n）種狀態(tài)，根據(jù)輸入的信號(hào)可以從一種狀態(tài)變?yōu)榱硪环N狀態(tài)。為了更清楚地說明實(shí)際生活中存在的有窮狀態(tài)系統(tǒng)，我們簡(jiǎn)單介紹一個(gè)電子商務(wù)方面的例子。電子商務(wù)在日常生活中的一個(gè)應(yīng)用就是網(wǎng)上購(gòu)物，這里涉及三個(gè)互相關(guān)聯(lián)的方面——顧客、商店和銀行。為簡(jiǎn)單起見，假設(shè)只有一個(gè)顧客（而且只有一次購(gòu)物活動(dòng)），他已在銀行建立了賬戶。假設(shè)商店也在銀行建立了賬戶。顧客可以決定把賬戶上的錢傳送給商店以購(gòu)買商品，然后商店從銀行拿到這筆錢并送貨給顧客。而且，顧客可以在一定時(shí)間內(nèi)選擇取消購(gòu)物。也就是說，顧客可以告訴銀行不再用這筆錢付購(gòu)物款。因此，三方之間的交互限于以下五種事件：（1）顧客決定付款購(gòu)物。顧客告訴商店購(gòu)買某種物品，并附帶上自己的銀行賬號(hào)。（2）顧客決定取消付款。顧客通知銀行，把購(gòu)物這筆錢保留在自己的銀行賬號(hào)上。（3）商店送貨給顧客。（4）商店兌換貨款。商店要求銀行把顧客購(gòu)物這筆錢劃撥到自己的銀行賬號(hào)上。（5）銀行將這筆錢轉(zhuǎn)賬。銀行把顧客購(gòu)物這筆錢劃撥給商店的賬號(hào)。

圖書封面

圖書標(biāo)簽Tags

無

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

---

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

---