包郵有限自動機理論(第四版)

作者：周益民等

出版社：科學(xué)出版社出版時間：2021-09-01

開本： 16開 頁數(shù)： 206

本類榜單：教材銷量榜

中圖價:¥69.6(7.9折) 定價 ~~¥88.0~~ 登錄后可看到會員價

加入購物車收藏

開年大促， 全場包郵

?新疆、西藏除外

本類五星書更多>

>
闖進數(shù)學(xué)世界――探秘歷史名題

闖進數(shù)學(xué)世界――探秘歷史名題

¥20.7¥32.8
>
中醫(yī)基礎(chǔ)理論

中醫(yī)基礎(chǔ)理論

¥51.7¥59
>
當代中國政府與政治(新編21世紀公共管理系列教材)

當代中國政府與政治(新編21世紀公共管理系列教材)

¥31.2¥48
>
高校軍事課教程

高校軍事課教程

¥12.4¥38
>
思想道德與法治(2021年版)

思想道德與法治(2021年版)

¥8.5¥18
>
毛澤東思想和中國特色社會主義理論體系概論(2021年版)

毛澤東思想和中國特色社會主義理論體系概論(2021年版)

¥8.5¥25
>
中醫(yī)內(nèi)科學(xué)·全國中醫(yī)藥行業(yè)高等教育“十四五”規(guī)劃教材

中醫(yī)內(nèi)科學(xué)·全國中醫(yī)藥行業(yè)高等教育“十四五”規(guī)劃教材

¥85.1¥99

商品詳情
商品評論(0條)

中圖價:¥69.6 加入購物車

版權(quán)信息
內(nèi)容簡介
目錄
節(jié)選

有限自動機理論(第四版) 版權(quán)信息

ISBN：9787030697967
條形碼：9787030697967 ; 978-7-03-069796-7
裝幀：一般膠版紙
冊數(shù)：暫無
重量：暫無
所屬分類：
教材
>
研究生/本科/專科教材
>
工學(xué)

有限自動機理論(第四版) 內(nèi)容簡介

形式語言與自動機理論是計算機科學(xué)與技術(shù)專業(yè)的一門重要課程。本書簡述形式語言基本內(nèi)容，包括文法的分類、構(gòu)造方法和語言間運算的封閉性。系統(tǒng)地論述三類有限自動機——有限狀態(tài)自動機、下推自動機和圖靈機的基礎(chǔ)理論。從文法產(chǎn)生語言和自動機識別語言的角度對語言進行討論，介紹了文法與等價的自動機之間的轉(zhuǎn)換方法以及有限自動機的一些典型應(yīng)用。本書以新的思維方式為讀者提供了一把鑰匙，主要培養(yǎng)讀者的獨立思考能力、抽象思維能力、使用符號化的系統(tǒng)描述程序設(shè)計語言或自然語言的語法結(jié)構(gòu)的能力以及構(gòu)造自動機的能力。本書可作為高等學(xué)校計算機科學(xué)與技術(shù)學(xué)科各專業(yè)研究生的教材或參考書，也可作為汁算機應(yīng)用領(lǐng)域的廣大科技人員的參考書。

有限自動機理論(第四版) 目錄

目錄
第1章基礎(chǔ)知識 1
1.1 集合及其運算 1
1.2 關(guān)系 3
1.2.1 二元關(guān)系 3
1.2.2 等價關(guān)系 3
1.2.3 關(guān)系合成 4
1.3 證明和證明的方法 5
1.3.1 反證法 5
1.3.2 歸納法 6
1.3.3 遞歸的定義與歸納證明 7
1.4 圖與樹 7
1.5 語言 8
1.6 常用術(shù)語 8
1.7 形式語言與自動機的發(fā)展 11
習(xí)題1 13
第2章形式語言 14
2.1 例子語言 14
2.2 文法和語言的關(guān)系 19
2.2.1 文法 19
2.2.2 語言 21
2.2.3 文法和語言的3類問題 22
2.3 Chomsky對文法和語言的分類 23
2.4 文法產(chǎn)生語言 27
2.5 無用非終結(jié)符 35
2.6 推導(dǎo)樹 35
2.7 空串定理 38
2.8 消除左遞歸 39
2.8.1 消除直接左遞歸 39
2.8.2 消除間接左遞歸 40
2.9 上下文無關(guān)文法的另一種表示 42
2.10 語言之間的運算及運算的封閉性 43
2.10.1 語言之間的基本運算 43
2.10.2 語言之間的運算的封閉性 44
2.10.3 語言之間的其他運算 48
2.11 正則表達式和正則集 50
習(xí)題2 53
第3章有限狀態(tài)自動機 55
3.1 有限狀態(tài)自動機簡介 55
3.2 確定有限狀態(tài)自動機接收的語言 57
3.3 確定有限狀態(tài)自動機接收語言的例子 62
3.4 不確定有限狀態(tài)自動機 74
3.4.1 不確定有限狀態(tài)自動機簡介 75
3.4.2 不確定有限狀態(tài)自動機的確定化 76
3.5 帶有ε動作的有限狀態(tài)自動機 82
3.6 有限狀態(tài)自動機的一些變形 89
3.6.1 雙向的有限狀態(tài)自動機 89
3.6.2 帶有輸出的有限狀態(tài)自動機 90
3.7 有限狀態(tài)接收機的存儲技術(shù) 94
3.8 有限狀態(tài)自動機應(yīng)用實例 96
習(xí)題3 109
第4章下推自動機 110
4.1 下推自動機簡介 110
4.1.1 確定的下推自動機 111
4.1.2 不確定的下推自動機 114
4.1.3 下推自動機接收語言的兩種方式 116
4.1.4 廣義下推自動機和單態(tài)下推自動機 120
4.2 上下文無關(guān)文法和范式 123
4.2.1 Chomsky范式 123
4.2.2 Greibach范式 124
4.3 下推自動機與上下文無關(guān)語言 126
4.4 下推自動機應(yīng)用實例 138
習(xí)題4 141
第5章圖靈機 143
5.1 圖靈機的基本模型 143
5.1.1 圖靈機的定義 143
5.1.2 圖靈機的構(gòu)造 146
5.2 圖靈機作為非負整數(shù)函數(shù)計算模型 153
5.3 圖靈機的構(gòu)造技術(shù) 156
5.3.1 圖靈機的存儲技術(shù) 156
5.3.2 圖靈機的移動技術(shù) 160
5.3.3 圖靈機掃描多個符號技術(shù) 161
5.3.4 圖靈機的多道技術(shù) 173
5.3.5 圖靈機的查訖技術(shù) 180
5.3.6 圖靈機的子程序技術(shù) 181
5.4 圖靈機變形 184
5.4.1 雙向無窮帶圖靈機 185
5.4.2 多帶多讀/寫頭圖靈機 188
5.4.3 不確定圖靈機 189
5.4.4 多維圖靈機 191
5.4.5 其他圖靈機 192
5.5 通用圖靈機 195
5.5.1 編碼目的 195
5.5.2 編碼方法 195
5.5.3 總結(jié) 198
5.6 圖靈機與短語結(jié)構(gòu)語言 198
5.7 線性有界的圖靈機與上下文相關(guān)語言 198
5.8 圖靈機應(yīng)用實例 199
習(xí)題5 205
參考文獻 207

展開全部

有限自動機理論(第四版) 節(jié)選

第1章基礎(chǔ)知識形式語言與自動機理論包括3方面的內(nèi)容：形式語言理論、自動機理論和形式語言與自動機等價性理論。本書主要討論自動機理論和形式語言與自動機等價性理論。本書內(nèi)容屬于理論計算機科學(xué)的理論范疇，所需的數(shù)學(xué)基礎(chǔ)知識較多。本章對形式語言和有限自動機理論中所需的數(shù)學(xué)基礎(chǔ)知識做扼要的介紹，內(nèi)容包括集合及其運算、關(guān)系、證明和證明的方法以及圖與樹的概念；同時對形式語言和自動機理論中的重要概念及相關(guān)術(shù)語做簡要介紹。 1.1 集合及其運算集合理論是計算機理論的重要基礎(chǔ)，也是形式語言和自動機理論的基礎(chǔ)。一些沒有重復(fù)的對象的全體稱為集合，而這些被包含的對象稱為該集合的元素。集合中元素可以按任意順序進行排列。一般來說，使用大寫英文字母表示一個集合。使用.代表空集，表示該集合未包含任何元素。若集合A包含元素x(也稱元素x屬于集合A)，則記為x∈A。若集合A未包含元素x(也稱元素x不屬于集合A)，則記為。若一個集合包含的元素個數(shù)是有限的，則稱該集合為有窮集合。若一個集合包含的元素個數(shù)是無限的，則稱該集合為無窮集合。對于任意的有窮集合A，使用|A|表示該集合包含的元素的個數(shù)，顯然。對于具體的集合，可以使用明確的、形式化的方法進行描述。對于元素個數(shù)較少的有窮集合，可以采用列舉法，即將集合的所有元素全部列出，放在一對花括號中。例如，集合A={0，1，2，3，4，5，6，7，8，9}，表示集合A由0、1、2、3、4、5、6、7、8、9共10個元素組成。對于集合元素較多的有窮集合和無窮集合，可以使用集合形成模式{x|P(x)}進行描述(也稱為命題法)；其中，x表示集合中的任一元素，P(x)是一個謂詞，對x進行限定。{x|P(x)}表示由滿足P(x)的一切x構(gòu)成的集合。可以使用自然語言或數(shù)學(xué)表示法來描述謂詞P(x)。例如，{n|n是偶數(shù)}或{n|nmod2=0}，都表示由所有偶數(shù)組成的集合。定義1.1 子集的定義。對于兩個集合A和B，若集合A的元素都是集合B的元素，則稱集合A包含于集合B 中(或稱集合B包含集合A)，記為A.B，并且稱集合A是集合B的子集。若A.B，且集合B中至少有一個元素不屬于集合A，則稱集合A真包含于集合B中(或稱集合B真包含集合A)，記為A.B，此時，稱集合A是集合B的真子集。兩個集合相等，當且僅當且B.A。注意：不是且。定義1.2 集合之間的運算。集合A與集合B的并(或稱為集合A與集合B的和)，記為A∪B，是由集合A的所有元素和集合B的所有元素合并在一起組成的集合： A∪B={x|x∈A或x∈B} 集合A與集合B的交，記為A∩B，是由集合A和集合B的所有公共元素組成的集合： A∩B={x|x∈A且x∈B} 集合A與集合B的差，記為A.B，是由屬于集合A但不屬于集合B的所有元素組成的集合：若，則將稱為集合B(關(guān)于集合A)的補，集合A稱為集合B的全集(論域)。思考：什么情況下，A∪B=A，A∩B=A，A.B=A？定義1.3 冪集的定義。設(shè)A為一個集合，那么A的冪集為A的所有子集組成的集合，記為2A，即例1.1 冪集的例子。集合A={1，2，3}，則A的冪集為當集合A為有窮集合時，如果集合A包含的元素個數(shù)為n，那么集合2A的元素個數(shù)(集合A的所有子集的個數(shù))為2n，這就是稱2A為集合A的冪集的原因。當集合A為無窮集合時，仍然使用2A表示集合A的冪集，它也是無窮集合。注意：任何集合A的冪集2A的元素都是集合。空集.是任何集合的子集，因此也是任何集合A的冪集2A的子集。定義1.4 笛卡兒乘積的定義。集合A和B的笛卡兒乘積使用A×B表示(也簡記為AB)，它是集合 {(a，b)|a∈A且b∈B} A×B的元素稱為有序偶對(a，b)，總是A的元素在前，B的元素在后。A×B與B×A一般不相等。例如，設(shè)A={a，b，c}，B={0，1}，則 A×B={(a，0)，(a，1)，(b，0)，(b，1)，(c，0)，(c，1)} 而 B×A={(0，a)，(0，b)，(0，c)，(1，a)，(1，b)，(1，c)} 思考：什么情況下，A×B=B×A？ 1.2 關(guān)系 1.2.1 二元關(guān)系定義1.5 二元關(guān)系的定義。設(shè)A和B為兩個集合，則A×B的任何一個子集稱為A到B的一個二元關(guān)系。若R為 A到B的關(guān)系，當(a，b)∈R時，可記為aRb。二元關(guān)系簡稱為關(guān)系。若A=B，則稱為A上的二元關(guān)系。例1.2 關(guān)系的例子。設(shè)A為正整數(shù)集合，則A上的關(guān)系“<”是集合 {(a，b)|a，b∈A且a　　即 {(1，2)，(1，3)， (2，3)，(2，4)， (3，4)，(3，5)， } 思考：如果集合A和B都是有窮集合，則A到B的二元關(guān)系有多少個？A到B的一個二元關(guān)系*多可以有多少個元素？*少可以有多少個元素？ 1.2.2 等價關(guān)系設(shè)R是集合A上的關(guān)系，那么若對A中的任何元素a，都有aRa，則稱R為自反的。若對A中的任何元素a和b，從aRb能夠推出bRa，則稱R為對稱的。若對A中的任何元素a、b和c，從aRb和bRc能夠推出aRc，則稱R為傳遞的。定義1.6 等價關(guān)系的定義。若關(guān)系R同時是自反的、對稱的和傳遞的，則稱R為等價關(guān)系。等價關(guān)系的一個重要性質(zhì)為：集合A上的一個等價關(guān)系R可以將集合A劃分為若干互不相交的子集，稱為等價類。對A中的每個元素a，使用[a]表示a的等價類，即 [a]={b|aRb} 等價關(guān)系R將集合A劃分成等價類的數(shù)目稱為該等價關(guān)系的指數(shù)。例1.3 等價關(guān)系的例子。考慮非負整數(shù)集合N上的模3同余關(guān)系R： R={(a，b)|a，b∈N且a mod 3=b mod 3} 則集合 {0，3，6，，3n， } 形成一個等價類，記為[0]。集合 {1，4，7，，3n+1， } 形成一個等價類，記為[1]。集合 {2，5，8，，3n+2， } 形成一個等價類，記為[2]。由于 N=[0]∪[1]∪[2] 因此R的指數(shù)為3。 1.2.3 關(guān)系合成關(guān)系是可以合成的。定義1.7 關(guān)系合成的定義。設(shè)是集合A到B的關(guān)系，設(shè)R2.B×C是集合B到C的關(guān)系，則R1和R2的合成是集合A到C的(二元)關(guān)系。R1和R2的合成記為R1vR2，則有 R1vR2={(a，c)|(a，b)∈R1且(b，c)∈R2} 例1.4 關(guān)系合成的例子。設(shè) R1和R2是集合{1，2，3，4}上的關(guān)系，定義1.8 關(guān)系的n次冪的定義。設(shè)R是S上的二元關(guān)系，則關(guān)系的n次冪Rn有如下遞歸定義：定義1.9 關(guān)系的閉包定義。設(shè)R是S上的二元關(guān)系，R的正閉包R+定義為 (1) R∈R+； (2)若(a，b)，(b，c)∈R+，則(a，c)∈R+； (3)除(1)和(2)外，R+不再含有其他任何元素，即 R+=R∪R2∪R3∪ 且當S為有窮集合時，有 R+=R∪R2∪R3∪ ∪R|S| 設(shè) R是S上的二元關(guān)系，R的克林尼(Kleene)閉包R*定義為例1.5 關(guān)系閉包的例子。設(shè)R1和R2是集合{a，b，c，d，e}上的二元關(guān)系，且 R1={(a，b)，(c，d)，(b，d)，(b，b)，(d，e)} R2={(a，a)，(b，c)，(d，c)，(e，d)，(c，a)} 求R1vR2，R1+，R1*。 (1)R1vR2={(a，c)，(c，c)，(b，c)，(d，d)} (2)R1+={(a，b)，(c，d)，(b，d)，(b，b)，(d，e)，(a，d)，(a，e)，(c，e)，(b，e)} (3)R1*={(a，a)，(b，b)，(c，c)，(d，d)，(e，e)}∪R1+ 1.3 證明和證明的方法形式語言和有限自動機有很強的理論性，許多論斷是以定理的形式給出的，而定理的正確性是需要進行證明的。形式語言和有限自動機理論中定理的證明，大多使用反證法和歸納法進行。 1.3.1 反證法反證法也稱為歸謬法。利用反證法證明一個命題時，一般步驟如下。 (1)假設(shè)該命題不成立。 (2)進行一系列的推理。 (3)如果在推理的過程中，出現(xiàn)了下列情況之一： ①得出的結(jié)論與已知條件矛盾； ②得出的結(jié)論與公理矛盾； ③得出的結(jié)論與已證明過的定理矛盾； ④得出的結(jié)論與臨時的假定矛盾； ⑤得出的結(jié)論自相矛盾；則可以斷言“假設(shè)該命題不成立”的假定是不正確的。 (4)肯定原來的命題是正確的。例1.6 反證法舉例。利用反證法證明 2是無理數(shù)。證明：假設(shè)2不是無理數(shù)，那么2是有理數(shù)，則2可以記為n，而且n和m是互m質(zhì)的，即n和m的*大公約數(shù)為1。則所以，n是偶數(shù)。令n=2k，則 (2k)2=2m2 4k2=2m2 2k2=m2 所以，m是偶數(shù)。 n和m都是偶數(shù)，與n和m的*大公約數(shù)為1矛盾。所以假設(shè)不成立，因此得證2是無理數(shù)。思考：18是完全平方數(shù)嗎？ 1.3.2 歸納法歸納法就是從特殊到一般的推理方法。歸納法分為完全歸納法和不完全歸納法兩種形式。完全歸納法是根據(jù)一切情況的分析而做出的推理。由于必須考慮所有的情況，所以得出的結(jié)論是完全可靠的。不完全歸納法是根據(jù)一部分情況做出的推理，因此它不能作為嚴格的證明方法。在形式語言與有限自動機理論中，大量使用數(shù)學(xué)歸納法來證明某個命題。數(shù)學(xué)歸納法可以使用“有限”的步驟來解決“無限”的問題。數(shù)學(xué)歸納法的步驟如下。假定對于一切非負整數(shù)n，有一個命題M(n)： (1) M(0)為真； (2)設(shè)對于任意的k≥0，M(k)為真；若能夠推出M(k+1)為真，則對一切n≥0，M(n)為真。因此，在使用數(shù)學(xué)歸納法證明某個關(guān)于非負整數(shù)n的命題P(n)時，只需要證明(1)、(2)兩點即可。第(1)步稱為歸納基礎(chǔ)，第(2)步稱為歸納步驟。第(2)步中“設(shè)對于任意的k≥0，M(k)為真”稱為歸納假設(shè)。在實際應(yīng)用中，某些命題P(n)并非對n≥0都成立，而是對n≥N(N為大于0的某個自然數(shù))成立，此時，也一樣可以使用該歸納法。具體步驟如下。假定對于一切非負整數(shù)n，有一個命題M(n)： (1)M(N)為真；

商品評論(0條)

寫書評賺書幣

暫無評論……

書友推薦