第2章 文法 計(jì)算機(jī)專業(yè) 形式語(yǔ)言課件

第2章文法

?對(duì)任何語(yǔ)言L,有一個(gè)字母表￡,使得L=￡*。

?L的具體組成結(jié)構(gòu)是什么樣的？

?一個(gè)給定的字符串是否為一個(gè)給定語(yǔ)言的句子?如

果不是，它在結(jié)構(gòu)的什么地方出了錯(cuò)？進(jìn)一步

地，這個(gè)錯(cuò)誤是什么樣的錯(cuò)？如何更正？……。

?這些問(wèn)題對(duì)有窮語(yǔ)言來(lái)說(shuō)，比較容易解決。

?這些問(wèn)題對(duì)無(wú)窮語(yǔ)言來(lái)說(shuō)，不太容易解決。

?語(yǔ)言的有窮描述。

2011-11-19

第2章文法

?主要內(nèi)容

文法的直觀意義與形式定義，推導(dǎo)、文法產(chǎn)生

的語(yǔ)言、句子、句型；喬姆斯基體系，左線性文

法、右線性文法，文法的推導(dǎo)與歸約；空語(yǔ)句。

?重點(diǎn)

文法、推導(dǎo)、歸約、模型的等價(jià)性證明。

?難點(diǎn)

形式化的概念，文法的構(gòu)造。

2011-11-192

2.1啟不

-文法的概念最早是由語(yǔ)言學(xué)家們?cè)谘芯孔匀徽Z(yǔ)言

理解中完成形式化。

?歸納如下句子的描述：

⑴哈爾濱是美麗的城市。

⑵北京是祖國(guó)的首都。

⑶集合是數(shù)學(xué)的基礎(chǔ)。

⑷形式語(yǔ)言是很抽象的。

⑸教育走在社會(huì)發(fā)展的前面。

⑹中國(guó)進(jìn)入WTO。

2011-11-193

2.1啟不

?6個(gè)句子的主體結(jié)構(gòu)

V名詞短語(yǔ),V動(dòng)詞短語(yǔ)＞＜句號(hào),

V名詞短語(yǔ)＞=｛哈爾濱，北京，集合，形式語(yǔ)言，

教育，中國(guó)｝

V動(dòng)詞短語(yǔ)＞=｛是美麗的城市，是祖國(guó)的首都，是

數(shù)學(xué)的基礎(chǔ)，是很抽象的，走在社會(huì)發(fā)展的前

面，進(jìn)入WTO｝

v句號(hào)＞=｛。｝

2011-11-194

2.1啟不

?V動(dòng)詞短語(yǔ)〉可以是V動(dòng)詞〉V形容詞短語(yǔ),或者〈動(dòng)

詞,V名詞短語(yǔ),。

?V名詞短語(yǔ)＞=｛北京、哈爾濱、形式語(yǔ)言、中國(guó)、

教育、集合、WTO、美麗的城市、祖國(guó)的首都、

數(shù)學(xué)的基礎(chǔ)、社會(huì)發(fā)展的前面｝。

?V動(dòng)詞＞=｛是、走在、進(jìn)入｝。

?〈形容詞短語(yǔ)＞=｛很抽象的｝。

?把〈名詞短語(yǔ),V動(dòng)詞短語(yǔ)〉V句號(hào)》取名為V句子

2011-11-195

2.1啟示

集合V動(dòng)詞〉V名詞短語(yǔ)》

是數(shù)學(xué)的基礎(chǔ)

2011-11-196

2.1啟不

,表示成a-8形式

V句子〉fV名詞短語(yǔ)＞＜動(dòng)詞短語(yǔ)＞＜句號(hào)＞

〈動(dòng)詞短語(yǔ)〉fV動(dòng)詞〉V形容詞短語(yǔ)〉

V動(dòng)詞短語(yǔ)〉fV動(dòng)詞〉〈名詞短語(yǔ)〉

V動(dòng)詞〉一是

2011-11-197

2.1啟不

V動(dòng)詞〉T?走在

V動(dòng)詞〉一進(jìn)入

V形容詞短語(yǔ)＞一很抽象的

V名詞短語(yǔ)?北京

v名詞短語(yǔ)＞-＞哈爾濱

〈名詞短語(yǔ)〉-形式語(yǔ)言

2011-11-198

2.1啟不

〈名詞短語(yǔ)〉―中國(guó)

〈名詞短語(yǔ)〉-教育

〈名詞短語(yǔ)〉一集合

V名詞短語(yǔ)》—WTO

〈名詞短語(yǔ)>->美麗的城市

〈名詞短語(yǔ)〉->祖國(guó)的首都

〈名詞短語(yǔ)〉—數(shù)學(xué)的基礎(chǔ)

〈名詞短語(yǔ)〉-社會(huì)發(fā)展的前面

V句號(hào)>—。

2011-11-199

2.1啟不

?表示一個(gè)語(yǔ)言，需要4種東西

⑴形如〈名詞短語(yǔ)〉的“符號(hào)”

它們表示相應(yīng)語(yǔ)言結(jié)構(gòu)中某個(gè)位置上可以出現(xiàn)

的一些內(nèi)容。每個(gè)“符號(hào)”對(duì)應(yīng)的是一個(gè)集合，在

該語(yǔ)言的一個(gè)具體句子中，句子的這個(gè)位置上能且

僅能出現(xiàn)相應(yīng)集合中的某個(gè)元素。所以，這種“符

號(hào)”代表的是一個(gè)語(yǔ)法范疇。

⑵v句子》

所有的“規(guī)則”，都是為了說(shuō)明V句子》的結(jié)構(gòu)

而存在，相當(dāng)于說(shuō)，定義的就是〈句子,。

2011-11-1910

2.1啟示

⑶形如北京的“符號(hào)”

它們是所定義語(yǔ)言的合法句子中將出現(xiàn)的“符

號(hào)”。僅僅表示自身，稱為終極符號(hào)。

⑷所有的“規(guī)則”都呈af6的形式

在產(chǎn)生語(yǔ)言的句子中被使用，稱這些“規(guī)則”

為產(chǎn)生式。

2011-11-1911

2.2形式定義

?文法(grammar)

?G=(V,T,P,S)

-V——為變量(variable)的非空有窮集。

VA￡V,A叫做一個(gè)語(yǔ)法變量(syntactic

Variable),簡(jiǎn)稱為變量，也色叫做非終

極符號(hào)(nonterminal)。它表示一個(gè)語(yǔ)法

范疇(syntacticCategory)。所以，本文

中有時(shí)候又稱之為語(yǔ)法范疇。

2011-11-1912

2.2形式定義

-T------為終極符(terminal)的非空有窮

集。VaeT,a叫做終極符。由于V中變

量表示語(yǔ)法范疇，T中的字符是語(yǔ)言的句

子中出現(xiàn)的字符，所以，有VAT=0。

-S——Sev,為文法G的開始符號(hào)(start

symbol)o

2011-11-1913

2.2形式定義

-P-----為產(chǎn)生式(production)的非空有窮

集合。P中的元素均具有形式戊一6，

被稱為產(chǎn)生式，讀作：a定義為6。一其

中a￡(VUT)+,且a中至少有V中元素

的一個(gè)出現(xiàn)。/3e(vuT)\a稱為產(chǎn)生

式af8的左部，8稱為產(chǎn)生式

的右部。產(chǎn)生式又叫做定義式或者語(yǔ)法

規(guī)則。

2011-11-1914

2.2形式定義

?例2-1以下四元組都是文法。

⑴({A},{0,1},{A.01,Af0A1,Af1A0},A)。

⑵({A},{0,1},{Af0,Af0A},A)o

⑶({A,B},{0,1},{A.01,AfOALAf1A0,BfAB,

B.0},A)o

(4)({A,B},{0,1},{Af0,AfLA.0A,A.1A},

A)o

2011-11-1915

2.2形式定義

⑸({S,A,B,C,D},{a,b,c,d,#},{SfABCD,

Sfabc#,A->aaA,ABfaabbB,BCfbbccC,

cJcccC,CDfccd#,CDfd#,CDf#d},S)o

(6)({S},{a,b},{SfOOS,SfUS,Sf00,SfH},

S)o

2011-11-1916

2.2形式定義

,約定

(1)對(duì)一組有相同左部的產(chǎn)生式

，)?，

ci—>81JLa->8Z,??a->B11

可以簡(jiǎn)單地記為：

a-西凡卜??l8n

讀作：以定義為Sy或者62,…，或者并

且稱它們?yōu)橐援a(chǎn)生式。61，62,…，6n稱為

候選式(candidate)。

2011-11-1917

2.2形式定義

⑵使用符號(hào)

?英文字母表較為前面的大寫字母，如A,B,C,…

表示語(yǔ)法變量；

?英文字母表較為前面的小寫字母，如a,b,c,...

表示終極符號(hào)；

?英文字母表較為后面的大寫字母，如X,Y,Z,...

表示該符號(hào)是語(yǔ)法變量或者終極符號(hào)；

?英文字母表較為后面的小寫字母，如x,y,z,…

表示由終極符號(hào)組成的行；

?希臘字母a,6，丫…表示由語(yǔ)法變量和終極符號(hào)

組成的行

2011-11-1918

2.2形式定義

?例2-3四元組是否滿足文法的要求。

-({A,B,C,E},{a,b,c},{S-^ABC|abc,Dfe|a,

FBfc,ATA,E->abc|8},S)

-4種修改

(1)({A,B,C,E,S,D,F},{a,b,c,e},

jsfABC|abc,Dfe|a,FBfc,A-A,E-

abc|￡},S)o

(2)({A,B,C,E,S},{a,b,c},{SfABC|abc,

A-^A,E->abc|￡},S)。

(3)({A,B,C,E},{a,b,c},{AfA,E-

abc|8},A)o

(4)({A,B,C,E},{a,b,c},{AfA,E-

abc|E},E)o

2011-11-1919

2.2形式定義

?推導(dǎo)(derivation)

設(shè)G=(V,T,P,S)是一個(gè)文法，如果af

丫,6G(VUT)\則稱ya6在G中直接推導(dǎo)

出丫66。

Yoi8X138

讀作：丫以6在文法G中直接推導(dǎo)出y66。

“直接推導(dǎo)”可以簡(jiǎn)稱為推導(dǎo)(derivation),也

稱推導(dǎo)為派生。

2011-11-1920

2.2形式定義

?歸約(reduction)

-yaB6

-稱y8S在文法G中直接歸約成rot6,在不

特別強(qiáng)調(diào)歸約的直接性時(shí)，“直接歸約”可以

簡(jiǎn)稱為歸約。

2011-11-1921

2.2形式定義

1.推導(dǎo)與歸約表達(dá)的意思的異同。

2.推導(dǎo)與歸約和產(chǎn)生式不一樣。所以，凈口

一所表達(dá)的意思不一樣。

3.推導(dǎo)與歸約是一一對(duì)應(yīng)的。

4.推導(dǎo)與歸約的作用。

2011-11-1922

2.2形式定義

含泵含當(dāng)成(VUT)*上的二元關(guān)系。

⑴A含6：表示a在G中經(jīng)過(guò)n步推導(dǎo)出8；

6在G中經(jīng)過(guò)n步歸約成a。即，存在aj

%,…，an/￡(VUT)*使得a茬

%君a2，…，%-i及8。

⑵當(dāng)n=0時(shí)，有a=8。即a3a。

(3)oi^B：表示a在G中經(jīng)過(guò)至少1步推導(dǎo)出

8；8在G中經(jīng)過(guò)至少1步歸約成a。

2011-11-1923

2.2形式定義

*

⑷a=>8：表示a在G中經(jīng)過(guò)若干步推導(dǎo)出

13；%在G中經(jīng)過(guò)若干步歸約成a。

分別用=>、B、3、3代替

+*n

多、含、m、m。

2011-11-1924

2.2形式定義

?例2-4設(shè)G=({A},{a},{A->a|aA},A)

AnaA使用產(chǎn)生式AfaA

naaA使用產(chǎn)生式AfaA

naaaA使用產(chǎn)生式A—aA

naaaaA使用產(chǎn)生式AfaA

na…aA使用產(chǎn)生式A—aA

na…aa使用產(chǎn)生式Afan

2011-11-1925

2.2形式定義

AnaA使用產(chǎn)生式AfaA

=^>aaA使用產(chǎn)生式AfaA

=^>aaaA使用產(chǎn)生式AfaA

=^>aaaaA使用產(chǎn)生式AfaA

???

=^>a...aA使用產(chǎn)生式AfaA

=^>a...aaA使用產(chǎn)生式AfaA

2011-11-1926

2.2形式定義

AAaaAAAnAAaaAaAA使用產(chǎn)生式AfaA

=>AaAaaAaAA使用產(chǎn)生式AfaA

nAaAaaAaaA使用產(chǎn)生式A->a

=>aaAaaAaaA使用產(chǎn)生式Afa

naaAaaAaaa使用產(chǎn)生式Afa

naaaAaaAaaa使用產(chǎn)生式AfaA

naaaaaaAaaa使用產(chǎn)生式A->a

=>aaaaaaaaaa使用產(chǎn)生式Afa

2011-11-1927

2.2形式定義

?例2?5設(shè)G=({S,A,B},{0,1},

{SfA|AB,Af0|0A,S)

對(duì)于n三L

A2(P首先連續(xù)n?l次使用產(chǎn)生式;

AfOA,最后使用產(chǎn)生式Af0；

A^>0nA連續(xù)n次使用產(chǎn)生式AfOA；

Bnl使用產(chǎn)生式Bfl；

Bn11使用產(chǎn)生式Bf11。

2011-11-1928

2.2形式定義

語(yǔ)法范疇A代表的集合L(A)={0,00,000,

0000,...}={0n|n^l}；

語(yǔ)法范疇B代表的集合L(B)={L11}

語(yǔ)法范疇S代表的集合L(S)=L(A)UL(A)L(B)

={0,00,000,0000,…}U{0,00,000,

0000,11}

={0,00,000,0000,…}U

U{01,001,0001,00001,…}U

U{011,0011,00011,000011,…}

2011-11-1929

OS6T-11-IT0Z

I+uWiu'OWUuiluiO。1uIVuO

I+iiWiu'OWUuilVrnO午uIVuO

l+iiWiu'OWUUIIUIOU+uIVuO

u^iu'OWUUIIVUIO<=uIVuO

OW!'OWU14-uIj+uO、uIVuO

OW!'OWUJ+uIVl+uO年uIVuO

OWUI+u1[+uOeuIVuO

OWU1+ulVi+uOUuIVuO

OWUuIVuO^V

"（V1【VO-V"0-v}'{【'0}"v}）=3殺9-Z,

太考庠紐VI

2.2形式定義

,幾點(diǎn)結(jié)論

-對(duì)任意的x￡E+,我們要使語(yǔ)法范疇D代表的

集合為住電三。｝,可用產(chǎn)生式組｛D'￡|xD｝來(lái)

實(shí)現(xiàn)。

-對(duì)任意的x,yeE+,我們要使語(yǔ)法范疇D代表

的集合為｛xnyn|n21｝,可用產(chǎn)生式組

｛Dfxy|xDy｝來(lái)實(shí)現(xiàn)。

-對(duì)任意的x,y￡￡+,我們要使語(yǔ)法范疇D代表

的集合為｛xnyn|n》O｝,可用產(chǎn)生式組

｛Df￡|xDy｝來(lái)實(shí)現(xiàn)。

2011-11-1931

2.2形式定義

?語(yǔ)言(language)

L(G)={w|weT*且Snw}

?句子(sentence)

VweL(G),w稱為G產(chǎn)生的一個(gè)句子。

?句型(sententialform)

G=(V,T,P,S),對(duì)于Va￡(VUT)*,如果S

na,則稱a是G產(chǎn)生的一個(gè)句型。

2011-11-1932

2.2形式定義

?句子W是從S開始，在G中可以推導(dǎo)出來(lái)的

終極符號(hào)行，它不含語(yǔ)法變量。

?句型。是從S開始，在G中可以推導(dǎo)出來(lái)的

符號(hào)行，它可能含有語(yǔ)法變量。

?例2?7給定文法G=({S,A,B,C,D},{a,

b,c,“#},{SfABCD|abc#,AfaaA,

ABfaabbB,BCfbbccCcC^cccC,

CDfccd#,CDfd#,CDf#d},S)

2011-11-1933

2.2形式定義

求句型aaaaaabbbbcccc#d的推導(dǎo)過(guò)程

S=>ABCD使用產(chǎn)生式S—ABCD

=^>aaABCD使用產(chǎn)生式AfaaA

=>aaaaABCD使用產(chǎn)生式AfaaA

=>aaaaaabbBCD使用產(chǎn)生式ABfaabbB

=>aaaaaabbbbccCD使用產(chǎn)生式BCfbbccC

=^>aaaaaabbbbccccCD使用產(chǎn)生式cCfcccC

=^>aaaaaabbbbcccc#d使用產(chǎn)生式CDf#d

2011-11-1934

2.2形式定義

求句型aaaaaaaaAbbccccd#的推導(dǎo)過(guò)程

S=>ABCD使用產(chǎn)生式SfABCD

=^>AbbccCD使用產(chǎn)生式BCfbbccC

=^>aaAbbccCD使用產(chǎn)生式AfaaA

=^>aaAbbccccd#使用產(chǎn)生式CDfccd#

=^>aaaaAbbccccd#使用產(chǎn)生式AfaaA

=>aaaaaaAbbccccd#使用產(chǎn)生式AfaaA

=^>aaaaaaaaAbbccccd#使用產(chǎn)生式AfaaA

2011-11-1935

2.2形式定義

?例2?8構(gòu)造產(chǎn)生標(biāo)識(shí)符的文法

G=（{v標(biāo)識(shí)符＞，v大寫字母》，v小寫字母》，v阿拉伯?dāng)?shù)字＞},{0,

1,…，9,A,B,C,…，Z,a,b,c,…，z},P,v標(biāo)識(shí)符〉）

P={V標(biāo)識(shí)符afV大寫字母＞|〈小寫字母〉，

〈標(biāo)識(shí)符〉fV標(biāo)識(shí)符＞＜大寫字母＞卜標(biāo)識(shí)符＞V小寫字母小標(biāo)識(shí)符＞V

阿拉伯?dāng)?shù)字〉，

V大寫字母〉'A|B|C|D|E|F|G|H|I|J|K|L|M|N|O,

v大寫字母〉'P|Q|R|S|T|U|V|W|X|Y|Z,

＜/b^^^＞^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|z,

v阿拉伯?dāng)?shù)字0|1|2|3|4|5|6|7|8|9}

2011-11-1936

2.2形式定義

G=（{＜標(biāo)識(shí)符〉，v頭〉，＜尾＞},{0,1,

2,???,9,A,B,C,???,Z,a,b,

C,…，z},P'，V標(biāo)識(shí)符》）

p'={〈標(biāo)識(shí)符＞f＜頭＞＜尾＞，

v頭〉.A|B|C|D|E|F|G|H|I|J|K|L|M|N

v頭〉'O|P|Q|R|S|T|U|V|W|X|Y|Z,

＜^＞^a|b|c|d|e|f|g|h|i|j|k|l|m|n

V頭〉fo|p|q|r|s|t|u|v|w|x|y|z，

2011-11-1937

2.2形式定義

V尾〉.8|0＜尾＞|1V尾＞|2V尾鄧V尾＞|4V尾＞|5v尾＞，

v尾＞.6V尾＞|7＜尾＞|8＜尾＞|9＜尾＞,

v尾＞-＞Av尾＞|Bv尾＞Qv尾＞|Dv尾平＜尾＞|Fv尾＞，

v尾》fGv尾＞|Hv尾＞|lv尾＞|Jv尾＞|Kv尾〉,

v尾〉.Lv尾＞|Mv尾＞|Nv尾＞Qv尾＞|Pv尾＞|Qv尾＞，

v尾〉.Rv尾＞|Sv尾＞|Tv尾＞|Uv尾＞|W尾〉,

v尾＞-＞W(wǎng)v尾＞|Xv尾＞|Yv尾＞|Zv尾＞|av尾＞|bv尾＞，

v尾》fcv尾＞|dv尾＞|ev尾＞|fv尾＞|gv尾〉,

v尾〉.hv尾＞『v尾＞|jv尾＞|kv尾＞[v尾＞|mv尾＞，

v尾》—nv尾＞|o＜尾＞|pv尾＞|qv尾＞|rv尾〉,

v尾＞—＞sv尾＞|tv尾＞|u＜尾＞|vv尾＞|wv尾＞|xv尾＞

v尾yv尾＞|zv尾＞}

2011-11-1938

標(biāo)識(shí)符id8n23,在文法G中的推導(dǎo)過(guò)程

〈標(biāo)識(shí)符,標(biāo)識(shí)符＞＜阿拉伯?dāng)?shù)字〉

nv標(biāo)識(shí)符＞3

nv標(biāo)識(shí)符＞v阿拉伯?dāng)?shù)字＞3

=＞v標(biāo)識(shí)符＞23

=＞＜標(biāo)識(shí)符＞＜小寫字母＞23

=＞v標(biāo)識(shí)符＞n23

nv標(biāo)識(shí)符＞v阿拉伯?dāng)?shù)字＞n23

=＞v標(biāo)識(shí)符＞8n23

nv標(biāo)識(shí)符＞＜小寫字母＞8n23

=＞v標(biāo)識(shí)符＞d8n23

=＞v小寫字母＞d8n23

2(m皿9=＞id8n23

2.2形式定義

標(biāo)識(shí)符id8n23,在文法G'中的推導(dǎo)過(guò)程

標(biāo)識(shí)符〉二＞V頭》V尾〉

niv尾〉

nidv尾》

nid8V尾》

nid811V尾〉

nid8112V尾,

nid823V尾,

nid8n23

2011-11-1940

2.2形式定義

?使用符號(hào)使文法更簡(jiǎn)潔

G"=({v標(biāo)識(shí)符＞},{b,a,d},{v標(biāo)識(shí)符b|a|v

標(biāo)識(shí)符＞b卜標(biāo)識(shí)符,a|v標(biāo)識(shí)符＞d},〈標(biāo)識(shí)符》)

G〃'=({L},{b,a,d},{L^b|a|Lb|La|Ld},L)

G〃〃=({L,H,T},{b,a,d},{LfHT,

Hfb|a,T-8|bT|aT|dT}5L)

2011-11-1941

2.3文法的構(gòu)造

?例2?9構(gòu)造文法G,使L(G尸{0,1,00,11)

-將文法的開始符號(hào)定義為這4個(gè)句子。

?G]=({S},{0,1},{Sf0,S.1,S->00,S->11},S)

-先用變量A表示0,用變量B表示1。

?G2=({S,A,B},{0,1},{S->A,S->B,SfAA,

S-?BB,Af0,B.1},S)

-基于G2,考慮“規(guī)范性”問(wèn)題。

?G3=({S,A,B},{0,1},{S->0,S->1,S-?0A,

S-?1B,Af0,B.1},S)

2011-11-1942

2.3文法的構(gòu)造

-可以在V、T中增加一些元素，以獲得“不同

的”文法。

?G4=({S,A,B,C},{0,1,2},{SfA,SfB,

SfAA,SfBB,Af0,B->1},S)

?G5=({S,A,B,C},{0,1,2},{S->A,S->B,

SfAA,SfBB,Af0,Bfl,CACS-21,

C->11,C-?2},S)

L(GJ=L(G2)=L(G3)=L(G4)=L(G5)

2011-11-1943

2.3文法的構(gòu)造

?等價(jià)(equivalence)

-設(shè)有兩個(gè)文法G］和G2，如果L(Gi尸MG2),則

稱Gi與G?等價(jià)。

,約定

-對(duì)一個(gè)文法，只列出該文法的所有產(chǎn)生式，且

所列第一個(gè)產(chǎn)生式的左部是該文法的開始符

號(hào)。

2011-11-1944

2.3文法的構(gòu)造

G1：S^O|1|OO|11

G2：SfA|B|AA|BB,Af0,Bf1

G3：S-0|l|0A|lB,Af0,B.1

G4：SfA|B|AA|BB,Af0,Bf1

G5：SfA|B|BB,Af0,Bfl,CACS-21,

C-11,J2

2011-11-1945

2.3文法的構(gòu)造

?例2-10

?L={0n|n^l}

G6：Sf0|0S

?L={0n|n^0}

G7：S-￡|0S

?L={02nl3n|n^0}

G8：EI00S111

2011-11-1946

2.3文法的構(gòu)造

?例2?11構(gòu)造文法G9,使L(G9)={w|w￡{a,

b,??.，z}+}o

G9：SfA|AS

A^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|z

?用S―A|AS生成A11。

?不可以用A—>a|b|c|…憶表示。

Afa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r閭t|u|v|w|x|y|z

?不可以用A->a8表示A->aaaaaaaa。

?不能用Afa11表示A可以產(chǎn)生任意多個(gè)a。

2011-11-1947

2.3文法的構(gòu)造

?例2?12構(gòu)造文法Gio，使

T

L(G10)={ww|we{0,1,2,3}+}。

文法

SfHE

H^O|1|2|3|OH|1H|2H|3H

E^0|l|2|3|E0|El|E2|E3

難以生成MG］。)。

2011-11-1948

2.3文法的構(gòu)造

?{wwT|we{0,1,2,3}+}的句子的特點(diǎn)

設(shè)亞=2正2…/口，從而有wT=an...a2aP故w

T

w=a1a2...anan...a2ax

TTT

滿足f(ww,i)=f(ww,|ww|-i+l)o

遞歸地定義L

一⑴對(duì)Va￡{0,1,2,3},aaeL；

一⑵如果x￡L,貝U對(duì)Va￡{0,1,2,3},axaeL；

-⑶L中不含不滿足(1)、(2)任何其他的串。

2011-11-1949

2.3文法的構(gòu)造

根據(jù)遞歸定義中的第一條，有如下產(chǎn)生式組：

S-00I11I22I33

再根據(jù)遞歸定義第二條，又可得到如下產(chǎn)生式組:

SfOSOI1S1|2S2I3S3

從而，

G10：S-00|11|22|33|OSO|1S1|2S2|3S3

2011-11-1950

2.3文法的構(gòu)造

?例2?13構(gòu)造文法G管，使L(G]2)={W|W是我們習(xí)慣的十

進(jìn)制有理數(shù)}。

Gn：SfR|+R|-R

RfN|B

BfN.D

N->0|AM

D->0|MA

A->1|2|3|4|5|6|7|8|9

M-￡|OM|IM|2M|3M|4M|5M|6M|7M|8M|9M

2011-11-1951

2.3文法的構(gòu)造

?例2-14構(gòu)造產(chǎn)生算術(shù)表達(dá)式的文法：

⑴基礎(chǔ)：常數(shù)是算術(shù)表達(dá)式，變量是算術(shù)表達(dá)式；

⑵歸納：如果E2是表達(dá)式，則+E「/1、

E[+E)、ErE?、E/E?、EJE,、Fun(E1)

是算術(shù)表達(dá)式。其中Fun為函數(shù)名。

(3)只有滿足(1)和(2)的才是算術(shù)表達(dá)式。

G13：E^id|c|+E|-E|E+E|E-E|E*E|E/E|E**E|Fun(E)

習(xí)題：

給出句子id+id*id的兩個(gè)不同的推導(dǎo)和兩個(gè)不同的規(guī)約

2011-11-1952

2.3文法的構(gòu)造

?例2-15構(gòu)造產(chǎn)生語(yǔ)言{anbncn|n三1}的文法。

文法G=({SJ,{a,b},{Sifab|aS]b},SJ

產(chǎn)生的語(yǔ)言{a%nIn三1}形式上看起來(lái)與語(yǔ)言

{anbncn|n三1}也較接近。

G=({S乙2),{C乙},{S2->C乙IcS乙2),S2)產(chǎn)生的語(yǔ)

言是{cn|n^l}o

{anbncnn^l}#{anbn|n^l}{cn|n三1}

2011-11-1953

2.3文法的構(gòu)造

文法

SfS[S,

S「ab|aSjb

S2^c|cS2

不能產(chǎn)生語(yǔ)言

{anbncn|nNl}

而是產(chǎn)生語(yǔ)言

{anbnn^l}{cnn》l}

2011-11-1954

2.3文法的構(gòu)造

文法

G：Sfabc|aSbc

產(chǎn)生的語(yǔ)言為：

{an(bc)n|n^l}

焦點(diǎn)：交換b和c的位置。

2011-11-1955

2.3文法的構(gòu)造

G14：S^aBCIaSBC,

CBfBC

aBfab

bBfbb

bC->bc

cCfcc

GJ：S^abc|aSBc,

bB—bb

cB->Bc

2011-11-1956

習(xí)題

設(shè)￡二{a,b,c},構(gòu)造下列語(yǔ)言的文法。

①11=但叫叩1三0}

②L2={anbm|n,m^1}

nnn

③L3={aba|n^l}

nmk

④L4={aba|n5m5k^1}

⑤L5={awa|a￡X,w￡E+}

T+

⑥L6={XWX|X,WGE}

T+

⑦L7={W|W=W,WGE}

T

⑧L8={XXW|X,w￡￡+}

文法的喬姆斯基體系

?文法G=(V,T,P,S)

?G叫做0型文法(type0grammar),也叫做短

語(yǔ)結(jié)構(gòu)文法(phrasestructuregrammar,

PSG)O

?L(G)叫做。型語(yǔ)言。也可以叫做短語(yǔ)結(jié)構(gòu)語(yǔ)

言(PSL)、遞歸可枚舉集(recursively

enumerable,r.e.)o

2011-11-1958

文法的喬姆斯基體系

?G是0型文法。

?如果對(duì)于V。f8&P,均有|8|三口|成

立，則稱G為1型文法(type1grammar),

或上下文有關(guān)文法(contextsensitive

grammar;CSG)o

,L(G)叫做1型語(yǔ)言(type1language)或者上

下文有關(guān)語(yǔ)言(contextsensitive

language,CSL)。

2011-11-1959

文法的喬姆斯基體系

?G是1型文法

?如果對(duì)于V。f8&P,均有|8|三口|，并且

01￡V成立，則稱G為2型文法(type2

grammar),或上下文無(wú)關(guān)文5去(contextfree

grammar;CFG)o

,L(G)叫做2型語(yǔ)言(type2language)或者上下文

無(wú)關(guān)語(yǔ)言(contextfreelanguage,CFL)。

2011-11-1960

文法的喬姆斯基體系

?G是2型文法

?如果對(duì)于Vaf8@P,a-8均具有形式

Afw

A—>wB

其中A,BEV,weT+o則稱G為3型文法

(type3grammar),也可稱為正則文法

(regulargrammar,RG)或者正規(guī)文法。L(G)

叫做3型語(yǔ)言(type3language),也可稱為正

則語(yǔ)言或者正規(guī)語(yǔ)言(regularlanguage,RL)。

2011-11-1961

文法的喬女學(xué)斯基體系

上下文有關(guān)語(yǔ)言

上下文無(wú)關(guān)語(yǔ)言

文法分類舉例

（1）下列文法是RG,CFG,CSG和短語(yǔ)結(jié)構(gòu)文法。

G1:S->O|l|OO|ll

G3:S->O|1|OA|1B,AfO,Bf1

G6:Sf0|0S

（2）下列文法是CFG,CSG和短語(yǔ)結(jié)構(gòu)文法,但不是RG。

G9：SfA|AS

A->a|b|c|dMf|g|h|i|j|k|l|m|n|o|p|q|r閭t|u|v|w|x|y|z

G10：S-00|11|22|33|OSO|1S1|2S2|3S3

G\?：S.R|+R|-R

R—N|B

BfN.D

N-0|AM

D-0|MA

Af112|3|4|5|6|7|8|9

MfOM|IM|2M|3M|4M|5M|6M|7M|8M|9M

G13：E^id|c|+E|-E|E+E|E-E|E*E|E/E|E**E|Fun(E)

2011-11-1964

(3)下列文法是CSG和短語(yǔ)結(jié)構(gòu)文法,但不是

CFG和RG。

G14：S^aBC|aSBC,

CBfBC

aBfab

bBfbb

bCfbe

cC^cc

(4)下列文法是短語(yǔ)結(jié)構(gòu)文法,但不是

CSG,CFG和RG。

G5：SfA,SfB,S-AA,SfBB,Af0,

B-?l,CACS-21,Cf11,Cf2

G7：S-￡|0S

G8：￡I00S111

G14：S^aBCIaSBC,

CBfBC

aBfab

bBfbb

bJbc

cCfcc

文法分類舉例

設(shè)1={0/11三1},試構(gòu)造滿足要求的文法G。

①G是RG。

②G是CFG,但不是RG。

③G是CSG,但不是CFGo

④G是短語(yǔ)結(jié)構(gòu)文法,但不是CSGo

文法的喬姆斯基體系

（1）如果一個(gè)文法G是RG,則它也是CFG、

CSG和短語(yǔ)結(jié)構(gòu)文法。反之不一定成立。

⑵如果一個(gè)文法G是CFG,則它也是CSG和

短語(yǔ)結(jié)構(gòu)文法。反之不一定成立。

⑶如果一個(gè)文法G是CSG,則它也是短語(yǔ)結(jié)

構(gòu)文法。反之不一定成立。

2011-11-1968

文法的喬姆斯基體系

相應(yīng)地：

(4)RL也是CFL、CSL和短語(yǔ)結(jié)構(gòu)語(yǔ)言。反之

不一定成立。

(5)CFL也是CSL和短語(yǔ)結(jié)構(gòu)語(yǔ)言。反之不一

定成立。

⑹CSL也是短語(yǔ)結(jié)構(gòu)語(yǔ)言。反之不一定成立

(7)當(dāng)文法G是CFG時(shí)，L(G)卻可以是RL。

(8)當(dāng)文法G是CSG時(shí),L(G)可以是RL、CSL。

(9)當(dāng)文法G是短語(yǔ)結(jié)構(gòu)文法時(shí)，L(G)可以是

-RL、CSL和CSL。69

文法的喬姆斯基體系

定理2口L是RL的充要條件是存在一個(gè)文法，

該文法產(chǎn)生語(yǔ)言L,并且它的產(chǎn)生式要么是形

如：Afa的產(chǎn)生式，要么是形如AfaB的產(chǎn)

生式。其中A、B為語(yǔ)法變量，a為終極符號(hào)。

?證明：

-充分性：設(shè)有G',L(G')=L,且G，的產(chǎn)生式

的形式滿足定理要求。這種文法就是RG。所以，

G'產(chǎn)生的語(yǔ)言就是RL,故L是RL。

2011-11-1970

文法的喬姆斯基體系

?必要性

構(gòu)造：用產(chǎn)生式組:

A—>a]A[

A1fa2A2

???

An.]一々n

代替產(chǎn)生式

A->^2***

2011-11-1971

文法的喬姆斯基體系

?用產(chǎn)生式組

A^a1A1

A]—>a2A2

???

Anjf打心

代替產(chǎn)生式

A->^2***B

2011-11-1972

文法的喬姆斯基體系

?證明L(G，)=L(G)o

施歸納于推導(dǎo)的步數(shù)，證明一個(gè)更一

般的結(jié)論：對(duì)于DA￡V,A=G+XOA=>

G,+X。因?yàn)镾￡V,所以結(jié)論自然對(duì)S成

立。

2011-11-1973

文法的喬姆斯基體系

?幾點(diǎn)注意事項(xiàng)

⑴我們是按照RG的一般定義來(lái)構(gòu)造一個(gè)與

之等價(jià)的文法的，這與讀者以前熟悉的根

據(jù)一個(gè)具體的對(duì)象構(gòu)造另一個(gè)對(duì)象是不同

的。在這里，可以使用的是非常一般的條

件——一個(gè)一般模型。這也是這類問(wèn)題的

證明所要求的。而且在本書的后面，將會(huì)

有更多這樣的情況。

2011-11-1974

文法的喬姆斯基體系

⑵為了證明一個(gè)特殊的結(jié)論，可以通過(guò)證明

一個(gè)更為一般的結(jié)論來(lái)完成。這從表面上

好像是增加了我們要證明的內(nèi)容，但實(shí)際

上它會(huì)使我們能夠更好地使用歸納假設(shè)，

以便順利地獲得我們所需要的結(jié)論。

2011-11-1975

文法的喬姆斯基體系

⑶施歸納于推導(dǎo)的步數(shù)是證明本書中不少問(wèn)

題的較為有效的途徑。有時(shí)我們還會(huì)對(duì)字

符串的長(zhǎng)度施歸納。

本證明的主要部分含兩個(gè)方面，首先是構(gòu)造,

然后對(duì)構(gòu)造的正確性進(jìn)行證明。這種等價(jià)

性證明的思路是非常重要的。

2011-11-1976

文法的喬姆斯基體系

?線性文法(linergrammar)

一設(shè)G=(V,T,P,S),如果對(duì)于Vaf8&P，

af6均具有如下形式：

—Afw

—AfwBx

一其中A,BEV,w,x￡T*,則稱G為線性文

法。

,線性語(yǔ)言(linerlanguage)

-L(G)叫做線性語(yǔ)言

2011-11-1977

文法的喬姆斯基體系

?右線性文法(rightlinergrammar)

一設(shè)G=(V,T,P,S),如果對(duì)于Vaf8&P，

af6均具有如下形式：

—Afw

—AfwB

一其中A,BEV,w,x￡T\則稱G為線性文法。

,右線性語(yǔ)言(rightlinerlanguage)

-L(G)叫做右線性語(yǔ)言。

2011-11-1978

文法的喬姆斯基體系

?左線性文法(leftlinergrammar)

一設(shè)G=(V,T,P,S),如果對(duì)于Vaf8&P，

af6均具有如下形式：

—Afw

—AfBw

一其中A,BEV,w,x￡T*,則稱G為線性文

法。

?左線性語(yǔ)言(leftlinerlanguage)

-L(G)叫做右線性語(yǔ)言。

2011-11-1979

文法的喬姆斯基體系

定理2?2L是一個(gè)左線性語(yǔ)言的充要條件是存

在文法G,G中的產(chǎn)生式要么是形如：Afa

的產(chǎn)生式，要么是形如AfBa的產(chǎn)生式，使

得L(G尸L。其中A、B為語(yǔ)法變量，a為終

極符號(hào)。

2011-11-1980

文法的喬姆斯基體系

定理2?3左線性文法與右線性文法等

價(jià)。

?按照定理2“的證明經(jīng)驗(yàn)，要想證明本定理,

需要完成如下工作：

-對(duì)任意右線性文法G,我們能夠構(gòu)造出對(duì)應(yīng)的

左線性文法G',使得L(G‘尸L(G)；

-對(duì)任意左線性文法G,我們能夠構(gòu)造出對(duì)應(yīng)的

右線性文法G',使得L(G'尸L(G)。

2011-11-1981

文法的喬姆斯基體系

?例2-17語(yǔ)言｛0123456｝的左線性文法和右線性文法

的構(gòu)造。

?右線性文法

Gr：Sr^0Ar

Ar—>lBr

Br^2Cr

Cr^3Dr

Dr^4Er

Er^5Fr

6

2011-11-1982

文法的喬姆斯基體系

?0123456在文法G「中的推導(dǎo)

Sr=>OAr使用產(chǎn)生式0A「

nOlBr使用產(chǎn)生式ArflBr

=>012Cr使用產(chǎn)生式B「f2Cr

=>0123Dr使用產(chǎn)生式C「f3Dr

=>01234Er使用產(chǎn)生式D「f4Er

=>012345Fr使用產(chǎn)生式E「f5Fr

=>0123456使用產(chǎn)生式6

2011-11-1983

文法的喬姆斯基體系

?左線性文法

G：S[.A]6

A[—^B]5

B「G4

GfD13

D[—>E[2

EifFJ

F1.0

2011-11-1984

文法的喬姆斯基體系

1

(1)

⑺

⑶(4)

2011-11-1985

文法的喬姆斯基體系

?0123456在文法G]中的推導(dǎo)

S]=A]6使用產(chǎn)生式S]-A]6

nB[56使用產(chǎn)生式A]-B]5

M456使用產(chǎn)生式B]-C]4

“3456使用產(chǎn)生式GfD13

nE123456使用產(chǎn)生式D]-E]2

nFJ234456使用產(chǎn)生式FJ

00123456使用產(chǎn)生式F1-0

2011-11-1986

文法的喬姆斯基體系

?0123456被歸約成文法G曾勺開始符號(hào)S

0123456

uF1234456使用產(chǎn)生式

-----1~F1-0

u523456使用產(chǎn)生式E1fFJ

uD3456使用產(chǎn)生式

----1~D]->E]2

uC456使用產(chǎn)生式

----1-G->D]3

UBQ6使用產(chǎn)生式B1fCH

二A6使用產(chǎn)生式A[->B]5

US1使用產(chǎn)生式S]>\6

2011-11-1987

文法的喬姆斯基體系

2011-11-1988

文法的喬姆斯基體系

定理2-4左線性文法的產(chǎn)生式與右線性文法

的產(chǎn)生式混用所得到的文法不是RG。

證明：設(shè)有文法

G15：S-0A

AfSl|l

nn

不難看出，L(G15)={0l|n^l}o我們構(gòu)造不出

RGG,使得L(G尸L(G”尸{Onln|n21}。因?yàn)?/p>

L(Gi5)={0nln|n21}不是RL。所以，心不是RG。

有關(guān):亥語(yǔ)言不是RL的證明我們將留到研究RL的

性質(zhì)時(shí)去完成。

2011-11-1989

2.5空語(yǔ)句

?形如Af￡的產(chǎn)生式叫做空產(chǎn)生式，也可叫

做￡產(chǎn)生式。

?在RG、CFG、CSG中，都不能含有空產(chǎn)生

式。所以，任何CSL中都不含有空語(yǔ)句

￡o從而CFL和RL中都不能含空語(yǔ)句￡。

?空語(yǔ)句￡在一個(gè)語(yǔ)言中的存在并不影響該

語(yǔ)言的有窮描述的存在性，甚至除了為生

成空語(yǔ)句￡外，空產(chǎn)生式可以不被用于語(yǔ)

言中其他任何句子的推導(dǎo)中。

2011-11-1990

2.5空語(yǔ)句

?允許CSL、CFL、RL包含空語(yǔ)句￡后，還會(huì)

給我們進(jìn)行問(wèn)題的處理提供一些方便。

?允許在RG、CFG、CSG中含有空產(chǎn)生式

?允許CSL、CFL、RL包含空語(yǔ)句8o

2011-11-1991

2.5空語(yǔ)句

定理2?5設(shè)G=(V,T,P,S)為一文法，則存在與G同

類型的文法G'=(V'，T,P'，S'),使得

L(G)=L(G'),但G，的開始符號(hào)S，不出現(xiàn)在G'

的任何產(chǎn)生式的右部。

證明：

構(gòu)造

當(dāng)文法G=(V,T,P,S)的開始符號(hào)S不出現(xiàn)在P中的任

何產(chǎn)生式的右部時(shí)，G就是所求

GF=(VU{Sr},T,P\SO

Pz=PU{SZ0f￡P(guān)}

2011-11-1992

2.5空語(yǔ)句

?證明L(G)=L(G，)

對(duì)任意的x￡L(G')，由文法產(chǎn)生的語(yǔ)

言的定義知，在G'中存在如下推導(dǎo)：

S，na使用產(chǎn)生式S，-a

n*x使用P，中的除S，fa以外

的其他產(chǎn)生式。

在推導(dǎo)an*x中使用的產(chǎn)生式都是P中

的產(chǎn)生式。因此，推導(dǎo)an*x在G中仍然成

立。

2011-11-1993

2.5空語(yǔ)句

由P'的定義知，必有Sf及￡P(guān)

所以，

Sna使用P中的產(chǎn)生式S—a

n*x使用P中的產(chǎn)生式

故，

L(GZ)cL(G)

2011-11-1994

2.5空語(yǔ)句

設(shè)G中存在如下推導(dǎo):

Sna使用P中的產(chǎn)生式Sfa

n*x使用P中的產(chǎn)生式

由P，=PU{SZ.aep},知道G，中,

S'na使用產(chǎn)生式S，TOL

n*x使用P，所包含的P中的其他

產(chǎn)生式。

故，L(G)cL(Gz)o

2011-11-19