有限自動機理論CH.ppt

有限自動機理論06016004,陳文宇 電子科技大學計算機科學與工程學院,聯(lián)系方式,B1-513,學時：（前8周） 學分： 考試：閉卷、筆試 考查：作業(yè)(3-4次)，不參加考試,教材：,有限自動機理論 陳文宇 電子科技大學出版社 2007.3,參考書,形式語言與自動機理論(第2版) （蔣宗禮 姜守旭 清華大學出版社） 形式語言與自動機 （陳有祺 機械工業(yè)出版社）,參考書,Introduction to Automata Theory, Languages, and Computation (Second Edition) 自動機理論、語言和計算導論 （John E. Hopcroft 清華大學出版社）,理論來源,形式語言和自動機的理論來源于 (1) Chomsky對自然語言的研究； (2) ALGOL 60語言的語法描述方式； (3)Turing、Kleene、Neumann、Huffman等 對自動機的研究。,形式語言與自動機的作用,形式語言和自動機的理論已經(jīng)成為計算機科學的理論基礎。 應用范圍已被擴展到生物工程、自動控制系統(tǒng)、圖象處理與模式識別等許多領域。,計算機學科的專業(yè)能力,計算思維能力 算法設計與分析能力 程序設計與實現(xiàn)能力 計算機系統(tǒng)的認知、分析、 設計和運用能力,計算(機)思維能力,形式化描述能力 抽象思維能力 邏輯思維方法,相關理論是計算機學科基礎。 理論方面的知識是計算機科學的真正靈魂。 這也是計算機科學與其他學科的重要區(qū)別。,有限自動機理論在科學領域中得到直接應用 對于計算機科學人才的計算思維能力的培養(yǎng)，也具有重要作用。,在本科階段, 以 觀察、描述、比較 分類、推斷、應用 的科學思維過程為主。,研究生階段，需要進一步進行抽象思維、邏輯思維、創(chuàng)造思維能力的培養(yǎng)。 本科生與研究生的根本區(qū)別在于研究生的需要 寬厚、堅實的理論知識。,第1章 基礎知識,本章將對有限自動機理論中所需的數(shù)學基礎知識作扼要的介紹。 包括集合及其運算、關系、證明的方法、圖與樹的概念；以及一些常用術語 和 形式語言與自動機的發(fā)展 。,內(nèi)容：,1.1集合及其運算 1.2 關系 1.3 證明和證明的方法 1.4 圖與樹 1.5 語言 1.6 常用術語 1.7 形式語言與自動機的發(fā)展,1.1 集合及其運算,一些沒有重復的對象的全體稱為集合，而這些被包含的對象稱為該集合的元素。 集合中元素可以按任意的順序進行排列。 使用大寫英文字母表示一個集合。,有窮集合和無窮集合,如果一個集合包含的元素個數(shù)是有限的，稱該集合為有窮集合。 如果一個集合包含的元素是無限的，稱該集合為無窮集合。 無窮集合又分為可數(shù)集(如正奇數(shù)集)和不可數(shù)集(如實數(shù)集)。,集合的定義方法：,列舉法 命題法,列舉法(窮舉法),對于有窮的，且元素個數(shù)較少的集合，可以采用列舉法，即將集合的所有元素全部列出，并放在一對花括號中。 例 集合A =1，2，3，4，5,對于某些無窮集合，也可以使用類似列舉的方法進行描述 如自然數(shù)集合： 0，1，2，3，,命題法,對于集合元素較多的有窮集合或者是無窮集合，可使用集合元素的形成模式 x | P(x) 進行描述。 其中：x表示集合中的任一元素, P(x)是一個謂詞，對x進行限定。,x | P(x) 表示 由滿足P(x)的一切x構(gòu)成的集合。 可以使用自然語言，或者數(shù)學表示法來描述謂詞P(x)。,例如：,n | n是偶數(shù) 或 n | n mod 2 = 0 表明了由所有偶數(shù)組成的集合。,集合的基數(shù),若集合A包含元素x，記為x A 反之， x A 對于有窮集合A，使用|A|表示該集合包含的元素的個數(shù)，也稱基數(shù)或勢 |A| = 0 A = 。,定義1-1 子集,設A, B是兩個集合，如果集合A中的每個元素都是集合B的元素，則稱集合A是集合B的子集(集合B是集合A的包集) A B 或 B A A, B是兩個集合，如果A B，且x B，但x A，則稱A是B的真子集 A B,兩個集合相等，當且僅當 A B且B A 注意： 不是A B且B A,定義1-2 集合的運算,集合A與集合B的并，記為AB。 集合A的所有元素和集合B的所有元素合并在一起組成的集合。 AB=x | xA 或 xB ,思考：,什么情況下： AB=A ？,集合A與集合B的交，記為AB 是由集合A和集合B的所有公共元素組成的集合。 AB= x | xA 且 xB ,思考：,什么情況下： A B=A ？,集合A與集合B的差，記為AB 屬于集合A但不屬于集合B的所有元素組成的集合。 AB= x |xA 且 x B ,思考:,什么情況下： A - B=A ？,如果B A，將AB稱為集合B（關于集合A）的補。 集合A稱為集合B的全集（或論域）,定義1-3 冪集,設A為一個集合，那么A的冪集為A的所有子集組成的集合 記為2A 2A=B | B A,例1-1,集合A=1，2，3，則A的冪集為: 2A= ， 1，2，3， 1，2，1，3，2，3， 1，2，3 ,冪集2A的元素個數(shù),當集合A為有窮集時，如果|A|=n，那么A的冪集2A的元素個數(shù)(集合A的所有子集的個數(shù))為2n。 （集合A的冪集表示為2A的原因）,定義1-4 笛卡兒積,集合A和B的笛卡兒乘積 A B（也簡記為AB） A B = (a, b) |a A且b B 當集合A、B為有窮集時 |A B|= |A| *| B|,例1-2,設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) 也可根據(jù)約定記為： A B=a0, a1, b0, b1, c0, c1,思考,什么情況下： A B = B A ?,練習,110之間的和為10的整數(shù)集合的集合, 1, 9, 2, 8, 3, 7, 4, 6, 1, 2, 7, 1, 3, 6, 1, 4, 5, 2, 3, 5, 1, 2, 3, 4 注意：沒有5，5,1.2 關系,1.2.1 二元關系 1.2.2 等價關系與等價類 1.2.3 關系的合成,1.2.1 二元關系,設A和B為兩個集合，則A B的任何一個子集稱為A到B的一個二元關系。 若R為A到B的關系，當 (a, b) R時，可記為aRb。 若A = B ，則稱為A上的關系。,思考：,如果集合A和B都是有窮集合，則 A到B的二元關系有多少個？ A到B的一個二元關系可以有多少個元素？,例1-3,設A為正整數(shù)集合，則A上的關系“”是集合 (a, b) | a, b A,且a b = (1, 2), (1, 3), (1, 4), . (2, 3), (2, 4), (2, 5), . . ,1.2.2 等價關系,設R是A上的二元關系 (1) 如果對于a A，都有 (a, a) R 則稱R是自反的。,(2) 如果對于a, b A (a, b) R (b, a) R 則稱R是對稱的。,(3)若對a, b, c A (a, b) R且(b, c) R(a, c) R 則稱R為傳遞的。,定義1-6,如果集合A上的二元關系R是自反的、對稱的和傳遞的 則稱R為等價關系。,等價關系的性質(zhì),等價關系的一個重要性質(zhì)為： 集合A上的一個等價關系R 可以將集合A劃分為若干個互不相交的子集-等價類,對A中的每個元素a，使用a表示a的等價類，即a=b | aRb。 等價關系R將集合A劃分成的等價類的數(shù)目-等價關系的指數(shù)。,例1-3,自然數(shù)集合N上的模3同余關系 R=(a, b)| a, b N, 且 a mod 3 = b mod 3。 是一個等價關系。,0,3,6,3n, 第1個等價類； 1,4,7,3n+1, 第2個等價類； 2,5,8,3n+2, 第3個等價類； 分別記為0，1和2。,N = 0 1 2 等價關系的指數(shù)為3,1.2.3 關系的合成,關系可以進行合成。,定義1-7,設R1 A B是A到B的(二元)關系 R2 B C是B到C 的(二元)關系 R1與R2的合成是A到C的(二元)關系 R1R2 = (a, c)| (a, b) R1且(b, c) R2 ,例1-5,R1和R2的是集合1,2,3,4上的關系 R1 =(1, 1), (1, 2), (2, 3), (3, 4) R2 =(2, 4), (4, 1), (4, 3), (3, 1), (3, 4) 則R1R2 =(1, 4), (2, 1), (2, 4), (3, 1), (3, 3) R2R1 =(4, 1), (4, 2), (4, 4), (3, 1), (3, 2),定義1-8 關系的n次冪,設R是S上的二元關系，則Rn遞歸定義為： (1) R0 = (a, a) | a S (2) Ri = Ri-1 R (i = 1, 2, 3, ),定義1-9 關系的閉包,設R是S上的二元關系， R的正閉包R+為 (1) R R+ ； (2) 若(a, b), (b, c) R+, 則 (a, c) R+ ； (3) 除(1)，(2)外， R+不再含有其他任何元素。,普通定義:R+,R+ = R R2 R3 ,且當S為有窮集時，有 R+ = R R2 R3 R|s|,關系的克林閉包,R* = R0 R+,例1-6,設R1= (a, b), (c, d), (b, d), (b, b), (d, e) R2= (a, a), (b, c), (d, c), (e, d), (c, a) 則R1 R2 = (a, c), (c, c), (b, c), (d, d),R1+ = (a, b), (c, d), (b, d), (b, b), (d, e), (a, d), (a, e), (c, e), (b, e) R1* = (a, a), (b, b), (c, c), (d, d), (e, e) R1+,1.3 證明和證明的方法,形式語言和有限自動機有很強的理論性，許多的論斷以定理的形式進行描述，而定理的正確性是需要進行證明的。 形式語言和有限自動機理論中定理的證明普遍使用反證法和歸納法,1.3.1 反證法 1.3.2 歸納法 1.3.3 遞歸定義與歸納證明,1.3.1反證法(歸謬法),利用反證法證明一個命題時，一般的步驟為： (1) 假設該命題不成立； (2) 進行一系列的推理； (3) 在推理的過程中如果出現(xiàn)了下列情況之一：,與已知條件矛盾； 與公理矛盾； 與已證過的定理矛盾； 與臨時的假定矛盾； 自相矛盾；,反證法(續(xù)),由于上述矛盾的出現(xiàn)，可以斷言“假設該命題不成立”的假設不正確； 從而肯定原命題正確。,反證法(續(xù)),反證法例子,是無理數(shù)。,演繹與歸納,演繹是從普遍性的理論知識出發(fā)，去認識個別的、特殊的現(xiàn)象的一種邏輯推理方法。 演繹的基本形式是三段論。 歸納是根據(jù)個別的、特殊的現(xiàn)象，得到普遍性知識的邏輯推理方法。,1.3.2 歸納法,歸納法是從特殊到一般的邏輯推理方法。 分為完全歸納法和不完全歸納法兩種形式。,完全歸納法是根據(jù)一切情況的分析而作出的推理。 由于必須考慮所有的情況，得出的結(jié)論是完全可靠的。,歸納法（續(xù)）,不完全歸納法是根據(jù)一部分情況作出的推理。 不能作為嚴格的證明方法。,在自動機理論中，普遍使用數(shù)學歸納法證明某個命題。,數(shù)學歸納法可以使用 “有限步驟” 解決“無限”問題。,數(shù)學歸納法,對于一切非負整數(shù)n的 命題M(n) (1) M(0)為真； (2) 假設對于任意的k 0，M(k)為真，能夠證明M(k + 1)為真 (3)則對一切n 0，M(n)為真。,第(1)步稱為歸納基礎 第(2) 步稱為歸納步驟 第(2)步中“設對于任意的k 0，M(k)為真”，稱為歸納假設,數(shù)學歸納法的簡化,對于0，證明結(jié)論成立； 假設結(jié)論對于n成立，證明結(jié)論對于n成立。,1.3.3 集合遞歸定義與歸納證明,遞歸定義 (1) 基礎 (2) 歸納 (3) 極小性限定(有限性),遞歸定義集合步驟,(1)基礎： 首先定義該集合中最基本的元素 x1, x2, x3, xm,(2)歸納： 對于該集合中的元素 x1, x2, x3, xn 使用某種組合方法對這些元素進行處理后所得的新元素在該集合中,(3)有限性： 只有滿足(1)和(2)的元素才在集合中,遞歸定義集合的優(yōu)點,除集合的基本元素(直接定義)外 集合中的元素的產(chǎn)生遵從相同的規(guī)律。,例1-6 Fibonacci數(shù),Fibonacci數(shù)組成的集合為： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ,(1)基礎： 0和1是最基本的兩個元素； (2)歸納： 若m是第i個元素,n是第i+1個元素 則第i + 2個元素為n + m; (3)只有滿足(1)和(2)的數(shù)，才是集合的元素,例,括號匹配的串構(gòu)成的集合的定義 ( ),( )( ),( ( ) ), （1）基礎： ( )是最基本的串,（2）歸納： 若S是括號匹配的串,則(S)是括號匹配的串 若S是括號匹配的串,則SS是括號匹配的串,練習,給出下列對象的遞歸定義 字符串的倒序,1.4 圖與樹,1.3.1 無向圖 1.3.2 有向圖 1.3.3 樹,圖,現(xiàn)實世界中，許多問題可以抽象成圖來表示。 直觀地，圖是由一些點和連接兩點的邊組成的。,定義1-10無向圖,設V是一個非空的有窮集合 E V V 稱G = (V, E)為一個無向圖。 其中，V稱為頂點集 E稱為無向邊集,無向圖中的邊都沒有方向 (vi, vj)和(vj, vi)表示的是同一條邊,無向圖頂點的度: 該頂點相關聯(lián)的邊的條數(shù) 記為 deg(v)，其中： v V,練習,設G = (V，E)為一個無向圖，則,數(shù)學歸納法,證明： (1)基礎。 當圖|E|=0時，圖中各結(jié)點的度均為0，因此,(2)歸納。 假設|E|=n時結(jié)論成立 |E|=n+1時，圖添加一條邊 令為(vi,vj)。,則 deg(vi)， deg(vj) 都增加1 而其它結(jié)點的度保持不變 因此在新圖中仍有,(3)由歸納法原理 結(jié)論對任意無向圖成立。,例,V = v1, v2, v3, v4, v5 E = (v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v5), (v3, v4), (v3, v5), (v4, v5) deg(v1) = deg(v2) =deg(v4) = deg(v5) = 3 deg(v3) = 4,有向圖,(vi, vj)表示的是從前導vi出發(fā)，到達后繼vj的一條邊。 (vi, vj)和(vj, vi)表示的是不同邊 有向圖頂點的度： 入度與出度,例 G2,V = v1, v2, v3, v4, v5 E = (v1, v2), (v1, v3), (v2, v3), (v3, v4), (v3, v5), (v4, v1),(v4, v5), (v5, v2),(v5, v4) ideg(v1)= 1,odeg (v1)= 2 ideg(v2) =2, odeg(v2) =1,定義1-12 有向路,設G = (V，E)為一個有向圖 如果對于0 i k 1，均有 (vi, vi+1) E 稱v0，v1，vk是一條(有向)路,有向回路,當v0 = vk時 稱為一條(有向)回路。,思考,從v1到v4有多少條路？,定義1-13 樹,設G = (V, E)為一個有向圖。 當G滿足如下條件時，稱G為一棵(有向)樹：,1) v V，v沒有前導，且v到樹中的其他頂點都有一條有向路，該頂點稱為樹G的根； 2)每個非根頂點有且僅有一個前導； 3) 每個頂點的后繼按其拓撲關系從左到右排序。,1.5 語言,任意字符的集合是一個字母表。 如 26個英文字母表；10個阿拉伯數(shù)字字母表；24個希臘字母表；二進制字母表,字母表有非空性、有窮性、單一性 一般使用表示字母表。,字符串,字母表中的字母按照某種順序排列成的字符的序列,語言研究的三個方面,1）如何給出一個語言的表示。 對于有窮語言，使用列舉法； 對于無窮語言，需要考慮語言的有窮描述。,語言研究的三個方面（續(xù)）,2）對于一個給定的無窮語言是否存在有窮描述（有窮表示）。 注意：并不是所有的無窮語言都存在有窮表示。,語言研究的三個方面（續(xù)）,3）具有有窮表示的語言的結(jié)構(gòu)以及結(jié)構(gòu)的描述問題。,1.6 常用術語,(1) 用代表空串，代表僅含有空串的集合。 (2) 用代表空集，表示一個元素都不包含的集合。 (3) 用代表字母表。,常用術語（續(xù)）,(4) 用代表兩個字符串與的連接（并置） 若 = a1a2a3an, = b1b2b3bm; 則= a1a2a3anb1b2b3bm。 特別： = =,用代表n的n次連接 0 = n = n-1 ，n0,(5) 用AB代表集合A與B的連接 A=a1,a2,a3,an B=b1,b2,b3,bm,AB= a1b1，a1b2，a1b3，a1bm， a2b1，a2b2，a2b3，a2bm， a3b1，a3b2，a3b3，a3bm， anb1，anb2，anb3，anbm ,注意：,A=A=,一般，AB與BA是不相等的。,思考:,AB與BA在什么情況下相等? 1)當 A=B； 2)A或B中有一個為,則 A=A=A 3)A和B中有一個為，則 A=A=,6)An代表集合A的n次連接(冪) A的n次冪定義為： (1) A0 = (2) An = An-1A n 1,7) A*代表A上所有字符串的集合 即表示集合A中的所有字符串進行任意次 連接而形成的串的集合,A*稱為集合A的閉包(克林閉包) A* = A0 A1 A2 An,例 A=0，1,A0= 即長度為0的0和1組成的串的集合 A1=A=0,1 即長度為1的0和1組成的串的集合,A2=AA=00,01,10,11 即長度為2的0和1組成的串集合 A3=A2A =000,001,010,011,100,101,110,111 即長度為3的0和1組成的串的集合, A* = A0 A1 A2 An =0和1 組成的所有的串 =w|w是0和1 組成的串,如果串是集合A的閉包中的串，也稱是集合A上的串。 對于任何集合A 有(A*)*= A*,8) A+稱為A的正閉包 A+=AA2A3An,A * 與 A+,A * = A+ A0 即 A * = A+ ,注意：,A0= *= += *= +=,思考,是否對于任意的集合A，都有 A+= A*-,辨析與思考與,|=1 |=0 A=A A= ,9）給定字母表，則*的任意子集L稱為字母表上的一個語言。 本質(zhì)上，語言L是字母表上的字符串形成的集合。,10)給定字母表， L是字母表上的一個語言，是L的一個字符串 稱為L的一個句子。,串的長度,|=0； |= n；若=a1a2a3an； 其中：ai，n0；,11)前綴和后綴： x,y,z*，且x=yz y是x的前綴； 如果z ，則稱y是x的真前綴； z是x的后綴； 如果y，則稱z是x的真后綴；,例1-13,串a(chǎn)bcde： 前綴：，a，ab，abc，abcd，abcde 真前綴：，a，ab，abc，abcd 后綴：，e，de，cde，bcde，abcde 真后綴：，e，de，cde，bcde,對于任意字符串x，x的前綴有 |x|+1 個 真前綴有 | x | 個,對于任何字符串x，x的任意前綴y有惟一的一個后綴z與之對應，使得x=yz，反之亦然； 對于任何字符串x，x的任意真前綴y有惟一的一個真后綴z與之對應，使得x=yz，反之亦然（除了以外）；,對于任何字符串x x是自身的前綴，但不是真前綴 x是自身的后綴，但不是真后綴,對于任何字符串x ， 是x的前綴，且是真前綴； 是x的后綴，且是真后綴；,思考：,對于， 前綴是？真前綴？ 后綴是？真后綴？,12)語言的前綴性質(zhì) 設L是某個字母表上的語言 如果L中的任何句子都是另一個句子的真前綴，則稱語言L具有前綴性質(zhì)。,例1-14,字母表0，1上的語言 L1=0n|n=0 具有前綴性質(zhì)； 語言L2=0n1|n=0 不具有前綴性質(zhì)。,語言與句子,設是一個字母表，L *, L稱為字母表上的一個語言 x L, x稱為L的一個句子。 語言的可分為有窮語言與無窮語言,語言的乘積,設1, 2是兩個字母表 L1 1*, L2 2*, 語言L1與L2的乘積是一個語言： L1L2=xy | x L1, y L2 該語言是字母表1 2 上的語言,語言的例子,字母表 0, 1上的一些語言： 00, 11 0, 1, 00, 11 00, 1*1 0, 1*1110, 1*,語言的n次冪,設是一個字母表，L *, L的n次冪是一個語言 (1) 當n = 0時， Ln = (2) 當n 1時， Ln = Ln-1 L,語言的例子,令 = 0, 1， L = 0, 1 L = 0, 1, 00, 01, 10, 11, = + L = , 0, 1, 00, 01, 10, 11, = *,L = 0n1n | n 1 L = 0n1m0k | n, m, k 1 L = 0n1m0k | n, m, k ,語言的閉包,L的正閉包L+是一個語言： L+ = L L2 L3 L的克林閉包L*是一個語言： L* = L0 L+,1.7形式語言與自動機的發(fā)展,語言學家Chomsky(喬姆斯基)最早從產(chǎn)生語言的角度研究語言。1956年，通過抽象，Chomsky將語言形式地定義為由一個字母表的字母組成的一些串的集合：對于任意語言L，有一個字母表，使得LC*。可以在字母表上按照一定的形成規(guī)則定義一個文法，該文法產(chǎn)生的所有的句子組成的集合就是該文法產(chǎn)生的語言。,1959年，Chomsky根據(jù)產(chǎn)生語言的文法的產(chǎn)生式的不同特點，將文法和對應產(chǎn)生的語言分為三大類。,數(shù)學家Kleene（克林）在19511956年間，從識別語言的角度來研究語言，給出了語言的另一種描述方式。Kleene在研究神經(jīng)細胞時建立了自動機模型，Kleene使用該模型來識別（接收）一個語言：按照某種識別規(guī)則構(gòu)造自動機，該自動機就定義了一個語言，該語言由自動機能夠識別的所有字符串構(gòu)成。,語言的兩種不同的定義方式進一步引起了人們的研究興趣。一個語言，可以采取不同的描述方式：文法產(chǎn)生語言和自動機識別語言。由于是同一個語言，兩種方式應該是等價的，也就存在兩種方式之間的等價的相互轉(zhuǎn)換方法。,Chomsky于1959年，將他本人的形式語言的研究成果和Kleene的自動機的研究成果結(jié)合起來，不僅確定了文法和自動機分別從產(chǎn)生和識別角度定義語言，而且證明了文法與自動機的等價性。此時，形式語言與自動機理論才真正誕生。并被置于數(shù)學的光芒之下。,形式語言與自動機理論出現(xiàn)后，迅速在計算機科學技術領域得到了應用。使用巴科斯-諾爾范式（BNF-Backus-Naur Form）成功地對高級程序設計語言ALGOL-60的詞法和語法規(guī)則進行了形式化的描述（實際上，巴科斯-諾爾范式就是上下文無關文法的產(chǎn)生式另一種表示方式）。這一成功，使得形式語言與自動機理論得到了進一步的發(fā)展。,尤其是上下文無關文法，被作為計算機程序設計語言語法的最佳近似描述得到了較為深入的研究。后來，人們又將上下文無關文法應用到了模式匹配和模型化處理等方面，而這些內(nèi)容都是算法描述和分析、計算復雜性理論和可計算性理論的研究基礎。,形式語言理論的研究對象與以前的所有語言研究不同，不止自然語言，而是人類一切語言：既有自然語言，也有人工語言，包括計算機編程的高級語言。喬姆斯基的形式語言理論得到了多重驗證，于是才為語言學界和計算機科學界所折服，“引發(fā)了語言學中伽利略式的科學革命的開端?！?喬姆斯基的形式語言理論得到過計算機科學的三種驗證。,驗證一：喬氏4型文法與4種語言自動機一一對應。,驗證二：計算機所使用的各種高級語言，如ALGOL、FORTRAN、PASCAL、C、LISP等，都遵循一種程序語言文法描述的范式，即巴科斯瑙爾范式。計算機科學家發(fā)現(xiàn)，巴科斯瑙爾范式等價于喬姆斯基的2型文法，即與上下文無關文法。而喬姆斯基的3型文法正則文法，在研究文字的計算機模式識別時，也被有效應用。于是，喬氏的4種類型文法被計算機科學界稱作喬姆斯基分類。,驗證三：喬姆斯基用形式語言理論的思想證明了計算機科學的一個重大理論問題：計算機程序語言是否