1、Part 1 形式語言基礎形式語言基礎主講教師 賀利堅2Part 1 主要內容提示主要內容提示內容教材出處一、語言的基本概念1.4.3 基本概念二、文法的形式定義(!)2.2 形式定義三、文法的構造方法(!)2.3 文法的構造四、文法的分類2.4 文法的喬姆斯基體系五、討厭的(有趣的)空語句2.5 空語句3一、語言的基本概念一、語言的基本概念1、字母表2、句子3、語言4字母表字母表G 定義1-33 字母表(alphabet) 、字母(letter)A 字母表是一個非空有窮集合；A 字母表中的元素稱為該字母表的一個字母。A 字母又叫做符號(symbol)、或者字符(character)。G 例1

2、=a, b, c, d, e, f, g, h, i , j , k , l , m , n , o , p , q , r , s , t , u , v , w , x , y , z2=0, 15G 字母表辨識A 3=aa, bb, cc字母表中有3個字母, 體現(xiàn)整體性（不可分性）A 4=a, a, b, b 字母表中有4個字母, a不同于a, 體現(xiàn)可辯認性（可區(qū)分性）A 5=a, b, a 不是字母表, a、a不可區(qū)分A 6= = 不是字母表, 要求非空字母表字母表6字母表字母表G 定義1-34 字母表的乘積(product) 12 12=ab|a1, b2 G 例1=0, 1 , 2

3、= a, b, c, d00, 01, 10, 1111 =a0, a1, b0, b1, c0, c1, d0, d121 = 0a, 0b, 0c, 0d, 1a, 1b, 1c, 1d12 =12 217字母表字母表G 定義1-35 字母表的n次冪 n 0= n=n-1 G 例=0, 1 是由中的0個字符組成 稱為空字符串（句子） 000, 001, 010, 011, 100, 101, 110, 11123 =00, 01, 10, 1112 =0, 1 0, 101=0=8字母表字母表G 定義1-36 正閉包 +、克林閉包*的正閉包 +=234的克林閉包*=0+=023G 例=0,

4、 1, 0, 1, 00, 01, 11, 000, 001, 010, 011, 100, * =0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, +=9句子句子G 定義1-37 句子(sentence) 是一個字母表, x*, x叫做上的一個句子。句子別稱： 字(word)、(字符、符號)行(line)、(字符、符號)串(string)。G 句子相等A 兩個句子被稱為相等的, 如果它們對應位置上的字符都對應相等。10句子句子G 定義1-39 句子的長度(length) x*, 句子 x 中字符出現(xiàn)的總個數(shù)叫做該句子的長度, 記作| x |。長度為

5、0的字符串叫空句子, 記作 。 G 例如： |abaabb|=6 |bbaa|=4 |=0 |bbabaabbbaa|=11 A是一個句子AA|=1A|= 0A |= 011句子句子G 定義1-40 句子的并置(concatenation) ：x, y*, x, y的并置是由串x直接相接串y所組成的，記作xy。并置又叫做連結。 G 定義1-40 串x的n次冪x0= xn=xn-1x, n 1G 例=a, bx=aab, y=abaa, xy=x= , y=ab, xy=x=aab, x0=aabaabaab, x3=abaababaa12句子句子G約定約定 用小寫字母表中較為靠前的字母a, b

6、, c, 表示字母表中的字母。 用小寫字母表中較為靠后的字母x, y, z, 表示字母表上的句子。 用xT表示x的倒序。例如, 如果x=abc, 則xT=cba。 13語言語言G 定義1-43 語言(language) 、語言中的句子 L *, L稱為字母表上的一個語言, xL, x叫做L的一個句子。 G 理解：A語言是字母表上所有句子集合的子集A語言是字母表上一些句子的集合A語言就是從通過組合規(guī)則從*中選擇一些合乎要求的句子形成的集合。14語言語言G 例：=0, 1 L1=0, 1 L2=00, 01, 10, 11 L3=0, 1, 00, 01, 10, 11, 000, =+ L4=,

7、 0, 1, 00, 01, 10, 11, 000, =* L5=0n|n1 L6=0n1n|n 1 L7=x|x +且x中0和1的個數(shù)相同 有窮語言: 含有窮個句子無窮語言: 有無窮個句子語言15語言語言G 定義1-44 語言的乘積(product)A L11*, L22*, A 語言L1與L2的乘積是12上的一個語言, 定義為：L1L2=xy| xL1, yL2例：L5=0n|n 1，L7=1n|n 1,L5L7= ？(A) 0n1n|n 1(B) 0n1m|n 1, m 1 16語言語言L5=0n|n 1L7=1n|n 1L6=0n1n|n 1有：L5L7 L6 證明：反證：000L5

8、 ，11 L7 但00011 L6不成立17語言語言G 例 (字母表上具有不同結構的語言) x|x=xT, x+ xxT|x+ xxT|x* xwxT|x, w+ xxTw|x, w+練習：當=a, b時，分別寫出各語言中的三個句子。18語言語言G 定義1-45 語言的n次冪L*, L的n次冪是一個語言, 定義為 當n=0時, Ln=。 當n1時, Ln= Ln-1L 。G 定義1-45 正閉包 L+=LL2L3L4 G 定義1-45 克林閉包 L*= L0LL2L3L4 19作業(yè)與指導作業(yè)與指導P40G 28題(2) (6) (8),再加一個要求：分別寫出各語言中的三個句子（2）L20n1m

9、|n,m1（6）L6xwxT|x,w（8）L8awa|a,w 參考L10n1nn 1。解：該語言的每一個句子由二部分構成，這二部分的組成依次為0和1，其中每部分的0或1的個數(shù)相等，且都不少于1個。句子有：01, 0011, 00011120作業(yè)與指導作業(yè)與指導G 32題(2)(4)(6)(9)(2)所有以0開頭，以1結尾的串。(4)所有最多有一對連續(xù)的0或者最多有一對連續(xù)的1的串(6)所有長度為偶數(shù)的串。(8)所有包含3個連續(xù)0的子串。A 參考：(1) 所有以0開頭的串。 解： L10 x | x*或： 00,1*21Part 1 主要內容提示主要內容提示內容教材出處一、語言的基本概念1.4.

10、3 基本概念二、文法的形式定義(!)2.2 形式定義三、文法的構造方法(!)2.3 文法的構造四、文法的分類2.4 文法的喬姆斯基體系五、討厭的(有趣的)空語句 2.5 空語句22基本問題基本問題G 對任何語言L，有一個字母表，使得L* G 語言的組成結構是分析、運用語言的基礎：A 一個給定的字符串是否為一個給定語言的句子?A 如果不是，它在結構的什么地方出了錯？A 這個錯誤是什么樣的錯？如何更正？。G 無論對有窮語言，還是無窮語言，都需要用有窮的手段進行描述。G 1956年，Chomsky在字母表上按照一定的規(guī)則定義文法，該文法產生的所有句子組成的集合就是該文法產生的語言。23二、文法的形式

11、定義二、文法的形式定義1、語言的描述2、文法的形式定義3、推導與歸約4、語法范疇5、語言、句子24語言的描述語言的描述 G 語言的描述是形式語言的第一個問題G 語言學家們在研究自然語言理解的形式化中提出文法的概念。 G 要求A 描述手段必須嚴格A 要能以有限的手段描述無限的語言G 可以利用句子的結構特點描述語言G 思路A 從句子的結構特性入手，用文法描述A 文法(Grammar)，對應自然語言中的語法25語言的描述語言的描述G 例,描述產生包含有單變量 i 和運算符 +, -, *, /, (, )的算術表達式的語言的文法如：i+i, i*i-i+i, (i-(i/i)+i)*iG 對應的構成

12、算法表達式的規(guī)則A單個變量是合法的最基本的串A若S是一個合法的串，則SAS是一個合法的串，其中A代表 +, -, *或/A若S是一個合法的串，則(S)是一個合法的串26語言的描述語言的描述產生式描述SiS SAS S(S)A +A -A *A /產生i *(i+i)的過程S SAS S*S i*S i*(S) i*(SAS) i*(S+S) i*(i+S) i*(i+i)或S SAS iAS i*S i*(S) i*(SAS) i*(iAS) i*(i+S) i*(i+i)極終符號極終符號 ：可出現(xiàn)在最終句子里：可出現(xiàn)在最終句子里非終極符號非終極符號：語言中某個位置上可以：語言中某個位置上可以

13、出現(xiàn)的內容出現(xiàn)的內容, 每一個符號代表一個語法每一個符號代表一個語法范疇，也稱為語法變量范疇，也稱為語法變量開始符號開始符號：描述語言的目的所在：描述語言的目的所在形如的產生式從開始符號用規(guī)則逐步替換可以得到句子文法中需要包含的文法中需要包含的4要素要素用有限的手段完成了對無限語言的描述27文法的形式定義文法的形式定義 G 定義2-1 文法(grammar)文法G是一個四元組，G=(V，T，P，S) A V為非終極符號/變量的非空有窮集。A T為終極符的非空有窮集。A P為產生式(production)的非空有窮集合。A S為開始符號，SV。 G 例: G=(S,A,+, -, *, /, (

14、, ), i,Si,S SAS, S(S),A +, A-,A*,A /,S )28文法的形式定義文法的形式定義G V非終極符號的非空有窮集。AV，A叫做A 一個語法變量(syntactic Variable)，簡稱變量A 或非終極符號(nonterminal)A 或語法范疇(syntactic Category)G T終極符(terminal)的非空有窮集。A aT，a叫做終極符A VT=。 G S 開始符號(start symbol)，SV。 G=(V，T，P，S)29文法的形式定義文法的形式定義G 文法示例G1=(A,0, 1, A01, A0A1, A1A0, A)G2=(A, 0,1

15、, A0, A0A, A)G3=(A,B,0,1,A01,A0A1,A1A0,BAB, B0, A)G4=(A, B,0, 1,A0, A1, A0A, A1A, A)G5=(S,0,1,S00S, S11S,S00, S11, S)文法是語言描述的模型系統(tǒng)30文法的形式定義文法的形式定義G P產生式產生式(production)的非空有窮集合的非空有窮集合A產生式，形如A讀作：定義為A 稱為左部，其中(VT)+，且中至少有V中元素的一個出現(xiàn)。A 稱為右部， (VT)*。A產生式又叫做定義式或者語法規(guī)則。 A第一個產生的左邊一定是開始符號G=(V，T，P，S)31文法的形式定義文法的形式定義G

16、約定約定 對一組有相同左部的產生式1,2, ,n可以簡單地記為：1|2|n讀作：定義為1,或者2 ,或者n稱1,2,，n為候選式(candidate)例：S i|SAS|(S)， A +|-|*|/32文法的形式定義文法的形式定義G 約定 使用符號A 英文字母表較前大寫字母表示語法變量, 如A,B,C,A 英文字母表較前小寫字母表示終極符號, 如a,b,c,A 英文字母表較后的大寫字母表示該符號是語法變量或者終極符號，如X,Y,Z, A 英文字母表較后的小寫字母表示由終極符號組成的行，如x,y,z,A 希臘字母,表示由語法變量和終極符號組成的行 33文法的形式定義文法的形式定義G兩個錯誤寫法A

17、錯誤1：Aaaaaaa寫作Aa6強調 (VT)*A錯誤2： A0|1|2|3|4|5|6|7|8|9寫作 A0|1|9 強調產生式有限34文法的形式定義文法的形式定義G文法的簡寫約定：只列出所有產生式，且第一個產生式的左部為開始符號G例G=(S,A,+, -, *, /, (, ), i ,Si, SSAS, S(S), A+, A-, A*, A/ ,S)簡寫為 Si|SAS|(S) A+|-| * |/35推導與歸約推導與歸約G 定義2-2 推導(derivation) 和歸約(reduction) 設G=(V，T，P，S)是一個文法，如果P, , (VT)*,則稱在文法G中直接推導出。在

18、文法G中直接歸約成。記作：讀作： 在文法G中直接推導出?！爸苯油茖А笨梢院喎Q為推導，也稱推導為派生“直接歸約”可以簡稱為歸約。G36推導與歸約推導與歸約G總結1推導與歸約表達的意思的不同。2推導與歸約和產生式不一樣。所以G 和所表達的意思不一樣。3推導與歸約是一一對應的。4推導與歸約的作用:B從開始符號起，經推導可以產生句子。 推導用于生成語言B由句子開始，經歸約后是否能回到開始符號？ 歸約用于識別語言37推導與歸約推導與歸約G G的推廣(1) Gn：存在1，2，n-1(VT)*，使得G1, 1G2 , , n-1G, 表示 在G中經過n步推導出; 在G中經過 n 步歸約成。(2)當n=0時，

19、有 = 。即 G0 。 (3) G+：表示在G中經過至少1步推導出； 在G中經過至少1步歸約成 。(4) G*：表示在G中經過若干步推導出； 在G中經過若干步歸約成 。 注： Gn應寫作nG38推導與歸約推導與歸約當問題中僅有一個文法時：用用代替代替n+*nG*G+G39推導與歸約推導與歸約G 例: 設G=(S,A,B,0,1,SA|AB,A0|0A,B1|11,S) A 從A開始，連續(xù)n-1次使用產生式A0A, (n 1) A n-1 0n-1AA 從A開始，連續(xù)n-1次使用產生式A0A，最后使用產生式A0，(n 1)A n 0n語法范疇A代表的集合 L(A)=0, 00, 000, 000

20、0, =0n|n 1；40語法范疇語法范疇G 對于文法G=(V, T, P, S)，若AV，A稱為語法變量或語法范疇G 例: G=(S,A,B, 0,1,SA|AB,A0|0A,B1|11, S) A A0|0A,語法范疇 A 代表的集合A B1|11，語法范疇 B 代表的集合 L(B)=A SA|AB, 語法范疇 S代表的集合 L(S)L(S)= L(A)L(A)L(B)L(A)=0, 00, 000, =0n | n11, 11=0, 00, 000, 0, 00, 000, 1, 11=0, 00, 000, 01, 001, 0001, 011, 0011, 00011, 41語法范疇

21、語法范疇例：設G=(A,0, 1, A01, A0A1, A)AA n 0nA1n，n 0AA + 0nA1n，n 1AA + 0n1n，n 1語法范疇A代表集合L(A)=0n1n|n142語法范疇語法范疇幾個常見語言及其產生式: 對任意 x, y +D|xxDyyyx2ny3n|n 05D|xDyxnyn|n 04D|xDxn|n 03Dxy|xDyxnyn|n 12Dx|xDxn|n11產生式組L(D)語法范疇代表的集合43語法范疇語法范疇G 有：Dxy|xDy,則L(D)=xnyn|n 1G 思考：L(D)可以由以下產生式組產生嗎？D D1D2D1 x|xD1D2 y|yD2G 回答：N

22、O，產生xnym|n 1, m 144語言、句子語言、句子G 定義定義2-3 語言語言(language) ，句子句子(sentence)設文法G=(V, T, P, S) , 則A L(G)=w | wT*且S * w為文法產生的語言語言是文法開始符號 S 對應的集合（語法范疇）A 對于wL(G)，w稱為G產生的一個句子句子是從S開始，在G中可以推導出來的終極符號行，它不含語法變量。45語言、句子語言、句子G定義定義2-4 句型句型(sentential form)設文法G=(V，T，P，S)，則A對于(VT)*，如果S * ，則稱 是G產生的一個句型。A句型是從S開始，在G中可以推導出來的

23、符號行，它可能含有語法變量。46語言、句子語言、句子G例：對例：對S i|SAS|(S), A +|-|*|/ 非句子、句型S)+i非句子、句型i+(*i)句型i+S/i句型(S+i)*S 句子(i+i)*i/i47語言、句子語言、句子G 定義2-5 文法的等價(equivalence)A 設有兩個文法G1和G2，如果L(G1)= L(G2)，則稱G1與G2等價。 G 同一語言可以由多個文法產生G 例：L(G1)=L(G2)= 0, 1, 00, 11 G1=(S,0,1,S0,S1,S00,S11,S) G2=(S,A,B,0,1,SA,SB,SAA,SBB,A0,B1,S) 48作業(yè)與指導

24、作業(yè)與指導P834、文法G的產生式集合如下，試給出句子aaabbbccc的一個推導和一個歸約SaBC | aSBCCBBCaBabbBbbbBb bCbccCccCcc6、文法G的產生式集合如下，請給出G中每個語法范疇代表的集合SaSa|aaSaa|aAaAbA|bbbA|bBBcB|cCCccC|DDDdD|d7 (4)、給定如下文法，請用自然語言描述它們定義的語言SaB|bAAa|aS|BAABb|bS|ABB49Part 1 主要內容提示主要內容提示內容教材出處一、語言的基本概念1.4.3 基本概念二、文法的形式定義(!)2.2 形式定義三、文法的構造方法(!)2.3 文法的構造四、文法

25、的分類2.4 文法的喬姆斯基體系五、討厭的(有趣的)空語句2.5 空語句50三、文法的構造方法三、文法的構造方法G任務：給出語言，構造生成語言的文法G同一語言，構造的文法不惟一G構造文法的思路有多種G給出語言構造文法無直接方法，需要憑借經驗GHow?Do it.Do it.51三、文法的構造方法三、文法的構造方法1、L(G)=0,1,00,11 2、L(G)=w|wa,b,z+3、L(G)=wwT|w0,1,2,3+4、L(G)=anbncn|n152L(G)=0,1,00,11 G 例例 構造文法構造文法G，使，使L(G)=0,1,00,11 (1)簡單枚舉 G1=(S,0,1,S0,S1,

26、S00,S11,S) (2)使用語法變量: L(A)=0,L(B)=1 G2=(S,A,B,0,1,SA,SB,SAA, SBB, A0, B1,S) 53G 例例 構造文法構造文法G，使，使L(G)=0，1，00，11(3)規(guī)范化的文法 A G3=(S,A,B,0,1,S0,S1,S0A,S1B, A0,B1,S) 正規(guī)文法（3型文法）A G3=(S,A,B,0,1,S0,S1,SA0,SB1, A0,B1,S) 左線性方法A 規(guī)范化文法提出了對文法的限制，便于掌握性質和利用。A 提倡使用盡可能簡單的規(guī)范化文法。54L(G)=w|wa,b,z+G預備預備 構造產生如下語言的文法L6=0n|n

27、1 L7=0n|n0L8=02n13n|n0 G8：S|00S111G6：S0|0SG7：S|0S55G例 構造文法G，使L(G)=w|w a,b,z+A要形成字母表 a,b,z中非空字符串，如：aa, ab, xyz, student,即Aw=a1a2an, 其中a1, a2 , , an a,b,zA設A為w中每一位置上的符號:Aa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zAw可表示為An , n1SA|ASL(G)=w|wa,b,z+56G例例(續(xù)續(xù))構造文法G，使L(G)=w|wa,b,z+A為L(G)=w|wa,b,z+ 設計

28、的文法G為: SA|ASAa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zA構造正規(guī)文法：受啟發(fā)于0n|n1的文法：S0|0SS a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zSaS|bS|cS|dS|eS|fS|gS|hS|iS|jS|kS|lS|mS|nS|oS|pS|qS|rS|sS|tS|uS|vS|wS|xS|yS|zS57思考：思考： 對對L(G)=w|w a,b,z* ?L(G)=w|wa,b,z+S a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r

29、|s|t|u|v|w|x|y|z| SaS|bS|cS|dS|eS|fS|gS|hS|iS|jS|kS|lS|mS|nS|oS|pS|qS|rS|sS|tS|uS|vS|wS|xS|yS|zS58L(G)=wwT|w 0,1,2,3+G 例構造文法G, 使L(G)=wwT|w0,1,2,3+wT為w的倒序，L(G)中句子的特點：A 形式化描述: 設w=a1a2an，wT= ana2 a1 A 特點: 從前數(shù)第i符號與從后數(shù)第i個一樣，特別地，從前數(shù)第1符號與從后數(shù)第1個一樣.A 從產生的角度: 開頭產生一個a, 在末尾一定要產生相同的符號.A 啟示: 以遞歸形式描述59G 例例(續(xù)續(xù)) 構造文

30、法G, 使L(G)=wwT|w0,1,2,3+A 遞歸地定義L 對a0，1，2，3，aa L；如果x L，則對a 0，1，2，3，axa L L中不含不滿足、 的任何其他的串。G 有S00 | 11 | 22 | 33S0S0|1S1|2S2|3S360G思考AL(G)=wawT|w0,1,2,3*， a 0,1,2,3 S 0|1|2|3|0S0|1S1|2S2|3S3AL(G)=wwT|w0,1,2,3* S |0S0|1S1|2S2|3S3AL(G)=wawT|w 0,1,2,3+, a0,1,2,3 S 0B0|1B1|2B2|3B3B 0|1|2|3|0B0|1B1|2B2|3B3L

31、(G)=wxwT|w,x 0,1,2,3+61G 方法總結：方法總結：結合語言結構的遞歸描述構造文法G 新湯熬老藥：新湯熬老藥：構造L(G)=w|wa,b,z+的文法A 語言結構的遞歸描述 對ca,b,z ，c L； 如果x L，則對c a,b,z ，cx L； L中不含不滿足 、任何其他的串。A 構造的文法： S a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zSaS|bS|cS|dS|eS|fS|gS|hS|iS|jS|kS|lS|mS|nS|oS|pS|qS|rS|sS|tS|uS|vS|wS|xS|yS|zS62L(G)=anbnc

32、n|n1例例 構造產生語言anbncn|n1的文法。解：簡化一下：用文法G：Sabc | aSbc能產生語言L(G)=an(bc)n | n1產生的句子形如：aaabcbcbc。設法換為: aaabbbccc由：a a a b c b c b c將cb換為bc : a a a b b c b c c繼續(xù)換: a a a b b b c c c63在G：Sabc | aSbc 的基礎上A 將b、c 用語法范疇 B、C代替A 加入CBBC規(guī)則有: SaBC | aSBCCBBCBbCca a a b c b c b c a a a b b c b c c a a a b b b c c cS *a

33、aaBCBCBC aaaBBCBCC aaaBBBCCC * aaabbbccc S * aaaBCBCBC * aaabcbcbc或 S * aaaBCBCBC* aaabbccbc但也有啟發(fā)：只有B、C順序好了，方可用b、c替換！64G 產生語言anbncn|n1的文法SaBC | aSBCCBBCaBabbBbbbCbccCcc進一步可簡化為：Sabc|aSBcbBbbcBBc 方法：替換B和C前要結合上下文N對B：B前為a、 b時，才可以替換為b：aBab，bBbbN對C：C前為b、 c時，才可以替換為c：bCbc，cCcc65作業(yè)與指導作業(yè)與指導8、 設=0,1, 請給出上下列語言的

34、文法（3）所有以11開頭, 以11結尾的串;（6）所有長度為偶數(shù)的串9、 設=a,b,c, 構造下列語言的文法（2）L2=anbm|n,m1（3）L3=anbnan|n1（4）L4=anbmak|n,m,k1（6）L6=xwxT| x,w+（7）L7=w | w = wT, w+66Part 1 主要內容提示主要內容提示內容教材出處一、語言的基本概念1.4.3 基本概念二、文法的形式定義(!)2.2 形式定義三、文法的構造方法(!)2.3 文法的構造四、文法的分類2.4 文法的喬姆斯基體系五、討厭的(有趣的)空語句2.5 空語句67四、文法的分類四、文法的分類1、文法的喬姆斯基體系2、語言L是

35、RL的充要條件3、線性文法(語言)68文法的喬姆斯基體系文法的喬姆斯基體系G 回顧文法定義： G=(V，T，P，S)A 對PA (VT)+，且中至少有V中元素的一個出現(xiàn)；A (VT)*G 喬姆斯基按文法中產生式的形式分類文法文法的喬姆斯基體系693型語言正則語言或者正規(guī)語言3型文法正則文法或者正規(guī)文法 Aw, AwBA，BV，wT+2型語言上下文無關語言2型文法上下文無關文法| |且V1型語言上下文有關語言1型文法上下文有關文法|0型語言短語結構語言遞歸可枚舉集0型文法短語結構文法(無額外要求）語言L(G)文法G對P文法的喬姆斯基體系文法的喬姆斯基體系 (VT)+，且中至少有V中元素的一個出現(xiàn)

36、； (VT)*70G 0/1/2/3型文法 (type 0/1/2/3 grammar)G 0/1/2/3型語言 (type 0/1/2/3 language)G 短語結構文法(phrase structure grammar, PSG) G 短語結構語言 (phrase structure language, PSL)G 遞歸可枚舉集 (recursively enumerable ，r.e. )G 上下文有關文法(context sensitive grammar,CSG) G 上下文有關語言(context sensitive language ,CSL)G 上下文無關文法(contex

37、t free grammar,CFG)G 上下文無關語言(context free language ,CFL)G 正則文法或者正規(guī)文法(regular grammar ,RG)G 正則語言或者正規(guī)語言(regular language ,RL)文法的喬姆斯基體系文法的喬姆斯基體系71type 3 RLtype 3 grammar RGAw, AwBA，BV，wT+type 2 language CFLtype 2 grammar CFG|and Vtype 1 language CSLtype 1 grammar CSG|type 0 language PSLr.e.type 0 gramm

38、ar PSG(no else）language L(G)grammar Gfor P文法的喬姆斯基體系文法的喬姆斯基體系72如果一個文法G是RG，則它也是CFG、CSG和PSG。反之不一定成立。如果一個文法G是CFG，則它也是CSG和PSG。反之不一定成立。如果一個文法G是CSG，則它也是PSG。反之不一定成立。RL也是CFL、CSL和PSL。反之不一定成立。CFL也是CSL和短語結構語言。反之不一定成立。CSL也是短語結構語言。反之不一定成立當文法G是CFG時，L(G)卻可以是RL。當文法G是CSG時，L(G)可以是RL、CSL。當文法G是短語結構文法時，L(G)可以是RL、CSL和CSL。

39、 文法的喬姆斯基體系文法的喬姆斯基體系73G思考A為什么對文法分類？（分類的意義、分類后要做什么） 文法的喬姆斯基體系文法的喬姆斯基體系74語言語言L是是RL的充要條件的充要條件定理 2-1 語言L是RL的充要條件是：存在一個產生語言L的文法，該文法的所有產生式形如Aa或AaB， A，BV，a T 。G L是RL, L由RG產生： RG: 對 P, 形如Aw, AwB, 其中A, B V, w T+G 該定理的重要意義：（1）簡化了RL的研究與應用；（2）證明過程給出了構造方法；（3）證明方法體現(xiàn)了本學科最基本的方法：B先構造：B再證明：存在？的確存在！給你一個瞧瞧！存在？的確存在！給你一個瞧

40、瞧！是嗎？顯然？嚴格證明給你看！是嗎？顯然？嚴格證明給你看！75G 定理 2-1 語言L是RL的充要條件是：存在一個產生語言L的文法，該文法的所有產生式形如Aa或AaB， A，B V，a T 。G 證明 ：A充分性（）：設有G，L(G)=L，且G的產生式形如Aa或AaB, A,BV，aT。這種文法就是RG。所以，G產生的語言就是RL，故L是RL。76G 必要性必要性 ()證明思路：A 由于L是RL，則存在RG，產生L。A 設G=(V,T,P,S)就是這個RG，G中的文法均形如： Aw, AwB，A, BV，wT+A 可以構造等價的文法G ，G中所有產生式形如： Aa, AaB, A, BV，a

41、TA 必要性證明需要兩步：B構造G ；B證明L(G)=L(G)A 想一想: 對 S aS|abA，A bcd ?SaSSaBBbAAbCCcDDd77(1)構造G : 對于RG G=(V,T,P,S) ，G中的文法均形如： Aw, AwB，A，BV，wT+不失一般性設：w=a1a2an, n1， a1,a2,anT則對產生式 A a1a2an，可替代的產生式組是： Aa1A1，A1a2A2 ， ， An-1an對產生式 A a1a2anB，可替代的產生式組是：Aa1A1 ， A1a2A2 ， ， An-1anB這樣得到新文法G =(V,T,P,S) A P中的產生式形如Aa, AaB, A，B

42、V，aTA V中包含中P中出現(xiàn)的所有語法變量。78例：S abcS bcAA d|dA構造的G 為:SaBBbCCcS bDD cAA dA dA即：SaB| bDBbCCcD cAA d|dA79(2) 證明 G和G等價，即 L(G)=L(G) 。需證明對x T*,x L(G) x L(G)，即 對x T*, SG* x 當且僅當 S G* x更一般地，對A V, x T*, AG* x當且僅當A G* x先證對 A V, x T*, AG* x，則 A G* x再證對 A V, x T*, A G* x ，則AG* x由于S V，結論自然也成立。（主要考慮產生式形式，不僅對S成立）80先證

43、對 A V, x T*, AG* x，則 A G* x當當n=1時時, AGx，必有Ax P，x T*, 設x=a1a2an, 則在G中有產生式: Aa1A1，A1a2A2 ， ， An-1an P進而, AG a1A1 G a1a2A2 G G a1a2an，所以，當n=1時，結論成立。設設nk時結論成立時結論成立，往證n=k+1時亦成立。設設n=k+1，x=x1x2，從而有AGx1B Gkx1x2設x1= a1a2ah ，則在G中有產生式Ax1B, G中有產生式 Aa1A1，A1a2A2 ， ， Ah-1ahB由于AGx1B Gkx1x2，所以B Gkx2根據歸納假設，必存在一個m，使B

44、Gmx2 故 AG a1A1 G a1 a2A2 G G a1a2ahBGm a1a2ahx2 由歸納法原理，由歸納法原理， 得證得證.81再證對 AV, xT*, A G * x ，則AG* x當當n=1時時, AG x，必有Ax P，必有Ax P,故 AGx成立。所以，當n=1時結論成立假設假設nk時結論成立時結論成立，往證n=k時結論亦成立。當當n=k(k2)，設x= a1a2ah-1，必有AG a1A1 G a1a2A2 G G a1a2A2 G a1a2Ah1 G a1a2ah1或AG a1A1 G a1 a2A2 G G a1a2Ah1 G a1a2ahB G a1a2ahx2,其

45、中A1,A2，,Ah-1是構造G時引入的變量對AG a1A1 G a1a2A2 G G a1a2A2 G a1a2Ah1 G a1a2ah1：推導所用的產生式依次為： Aa1A1，A1a2A2 ， ， Ah-1ah P必有A a1a2ah P ，所以 A Ga1a2ah82對AG a1A1 G a1 a2A2 G G a1a2Ah1 G a1a2ahB G a1a2ahx2:推導所用的產生式依次為： Aa1A1，A1a2A2 ， ， Ah-1ahB P必有A a1a2ahBP所以A Ga1a2ahBB在G中可以用不足k步推導出x2，由歸納假設，存在g，有A Ga1a2ahB Gga1a2ahx

46、2綜合以上兩種情況：AG a1A1 G a1a2A2 G G a1a2A2 G a1a2Ah1 G a1a2ah1或者AG a1A1 G a1 a2A2 G G a1a2Ah1 G a1a2ahB G a1a2ahx2結論對n=k時成立。由歸納法原理，結論對 A V成立。定理得證83語言語言L是是RL的充要條件的充要條件G語言L是RL的充要條件是：存在一個產生語言L的文法，該文法的所有產生式形如Aa或AaB， A, BV，aT 。84G 幾點啟示幾點啟示(1)等價性證明的重要思路：先構造，然后證明構造的正確性(2)歸納法證明：按推導步數(shù)、按字符串長度等(3)針對一般模型的構造(4)為了證明一個

47、特殊的結論，擴大到更為一般的結論來完成。（表面上好像增加了證明的內容，但實際上能夠更好地使用歸納假設。）語言語言L是是RL的充要條件的充要條件85線性文法線性文法(語言語言)G 定義定義2-7,8 設設G=(V，T，P，S)左線性語言left 左線性文法left Aw, ABwA，B V，w T*右線性語言right 正則語言右線性文法right 正則文法RGAw, AwBA，B V，w T*線性語言liner language線性文法。liner GrammarAw,AwBxA，B V，w，x T*語言L(G)文法G對 P線性文法線性文法(語言語言)不一定是左右線性文法不一定是左右線性文法(語言語言) ，反之成立，反之成立.86定理2-2 L是一個左線性語言的充要條件是存在產生語言L的文法G，G中的產生式形如：Aa或ABa ， A，B V，a T 。 證明類似定理2-1。對正則文法（語言）成立的結論，對左線