Chomsky文法體系及語(yǔ)言之間的運(yùn)算課件

Chomsky文法體系及語(yǔ)言之間的運(yùn)算在第一章中已指出對(duì)于程序的語(yǔ)法分析和自然語(yǔ)言的處理，形式化的文法描述方式起了重要的作用。本章介紹Chomsky的文法體系，語(yǔ)言的運(yùn)算和運(yùn)算的封閉性。4.1Chomsky的文法體系4.1.1文法的分類及文法之間的關(guān)系對(duì)于一般的短語(yǔ)結(jié)構(gòu)文法PSG=(∑，V，S，P)，產(chǎn)生式的形式是v→w，其中：v∈(∑UV)+，且至少包含一個(gè)非終結(jié)符；w∈（∑UV）*。定義4-1右線性文法的定義對(duì)于文法G=(∑，V，S，P)，若它的每個(gè)產(chǎn)生式都是下列形式之一：A→xC或者A→y；其中：A，C∈V，x∈∑*，y∈∑+；則文法G是右線性文法（也稱為正則文法RG）。如果一個(gè)語(yǔ)言L可以由右線性文法產(chǎn)生，則該語(yǔ)言是右線性語(yǔ)言。

定義4-2上下文無(wú)關(guān)文法的定義對(duì)于文法G，如果對(duì)于G中的任意產(chǎn)生式ν→ω，而ν只是一個(gè)非終結(jié)符，即A→ω，A∈V，ω∈（∑UV）*，則稱文法G為上下文無(wú)關(guān)文法CFG（簡(jiǎn)稱無(wú)關(guān)文法）。如果一個(gè)語(yǔ)言能由一個(gè)無(wú)關(guān)文法產(chǎn)生，則稱這個(gè)語(yǔ)言是上下文無(wú)關(guān)語(yǔ)言（簡(jiǎn)稱無(wú)關(guān)語(yǔ)言）。定義4-3上下文相關(guān)文法的定義對(duì)于文法G，如果G的每個(gè)產(chǎn)生式形如u→v，且0<|u|≤|v|；但若ε∈L(G)，則允許有S→ε，且S不出現(xiàn)在任何產(chǎn)生式的右邊；則稱文法G為上下文相關(guān)文法CSG（簡(jiǎn)稱相關(guān)文法）。如果一個(gè)語(yǔ)言能由一個(gè)相關(guān)文法產(chǎn)生，則稱這個(gè)語(yǔ)言是上下文相關(guān)語(yǔ)言（簡(jiǎn)稱相關(guān)語(yǔ)言）。根據(jù)以上的兩個(gè)定義，可以看出，一個(gè)無(wú)關(guān)的文法不一定是相關(guān)的文法，主要是空串產(chǎn)生式的情況。某些文法不滿足上述3類文法的要求；如

S→AB1AB→0該文法不是右線性文法，不是無(wú)關(guān)文法，也不是相關(guān)文法，只能屬于短語(yǔ)結(jié)構(gòu)文法。

Chomsky將文法分為四類，關(guān)系為：任意一個(gè)右線性文法本身是一個(gè)無(wú)關(guān)文法；本身不一定是相關(guān)文法；任意一個(gè)無(wú)關(guān)文法本身不一定是相關(guān)文法；設(shè)文法G=(∑，V，S，P)，則判斷G是哪類文法的方法如下：1、G是短語(yǔ)結(jié)構(gòu)文法；2、如果所有產(chǎn)生式都有右邊部分長(zhǎng)度大于等于左邊部分，那么G是上下文有關(guān)文法；3、如果如果所有產(chǎn)生式的左邊部分都是單個(gè)非終極符號(hào)，那么G是上下文無(wú)關(guān)文法；4、如果所有產(chǎn)生式的右邊部分都是以終極符號(hào)開(kāi)始、含有至多一個(gè)非終極符號(hào)、如果有非終極符號(hào)則出現(xiàn)在最右邊，那么G是正則文法。4.1.2語(yǔ)言之間的關(guān)系下面討論語(yǔ)言之間的關(guān)系。任意一個(gè)右線性語(yǔ)言文法本身是一個(gè)無(wú)關(guān)語(yǔ)言；一個(gè)上下文無(wú)關(guān)語(yǔ)言是不是一個(gè)上下文相關(guān)語(yǔ)言呢？從第二章可知：一個(gè)無(wú)關(guān)文法①?zèng)]有任何空串產(chǎn)生式，或者②僅有一個(gè)空串產(chǎn)生式S→ε，且S不出現(xiàn)在任何產(chǎn)生式的右邊則該文法本身就是一個(gè)相關(guān)文法；它產(chǎn)生的無(wú)關(guān)語(yǔ)言也就是一個(gè)相關(guān)語(yǔ)言；那么，如果一個(gè)無(wú)關(guān)文法中有一般的空串產(chǎn)生式（如A→ε，A是一個(gè)非終結(jié)符，且不是開(kāi)始符號(hào)），它產(chǎn)生的無(wú)關(guān)語(yǔ)言是不是相關(guān)語(yǔ)言呢？根據(jù)空串定理：G是一個(gè)上下文無(wú)關(guān)文法，存在一般的空串產(chǎn)生式A→ε，則存在另一個(gè)上下文無(wú)關(guān)文法G′使得：⑴L(G)=L(G′)；⑵若ε！∈L(G)，則G′中沒(méi)有任何空串產(chǎn)生式；⑶若ε∈L(G)，則G′中有一個(gè)空串產(chǎn)生式，S′→ε，且S′不出現(xiàn)在G′的其它任何產(chǎn)生式的右邊；（S′是G′開(kāi)始符號(hào)）實(shí)際上，G’是一個(gè)無(wú)關(guān)文法。也是一個(gè)相關(guān)文法。即：任意一個(gè)無(wú)關(guān)文法都可以改造為等價(jià)的一個(gè)相關(guān)文法，所以，任意一個(gè)無(wú)關(guān)語(yǔ)言也是一個(gè)相關(guān)語(yǔ)言。結(jié)論4-4Chomsky的文法體系：對(duì)于文法G=（∑，V，S，P），根據(jù)對(duì)產(chǎn)生式的不同限制，Chomsky將文法分為四類：文法G是3型文法，即右線性文法；文法G是2型文法，即上下文無(wú)關(guān)文法；文法G是1型文法，即上下文相關(guān)文法；文法G是0型文法，文法對(duì)產(chǎn)生式?jīng)]有任何限制；語(yǔ)言的分類是根據(jù)產(chǎn)生該語(yǔ)言的文法的分類進(jìn)行的。若一個(gè)語(yǔ)言L由某個(gè)i型文法產(chǎn)生，則它是i型語(yǔ)言。i=0,1,2,3。即語(yǔ)言L是3型語(yǔ)言，即右線性語(yǔ)言；若L能由某個(gè)3型文法產(chǎn)生。語(yǔ)言L是2型語(yǔ)言，即上下文無(wú)關(guān)語(yǔ)言；若L能由某個(gè)2型文法產(chǎn)生。語(yǔ)言L是1型語(yǔ)言，即上下文相關(guān)語(yǔ)言；若L能由某個(gè)1型文法產(chǎn)生。語(yǔ)言L是0型語(yǔ)言，即短語(yǔ)結(jié)構(gòu)語(yǔ)言(PSL)或遞歸可枚舉集，若L能由某個(gè)0型文法產(chǎn)生。定義4-5文法分類定義用Ψi（語(yǔ)言類）的概念來(lái)定義所有的i型語(yǔ)言；對(duì)于0≤i≤3Ψi={LС∑*|L=L（G），G是i型文法}。定理4-6語(yǔ)言分類定理Chomsky將語(yǔ)言分為四類，且有包含關(guān)系（真子集關(guān)系）：Ψ3СΨ2СΨ1СΨ04.2Chomsky的文法體系另一種描述目前，國(guó)內(nèi)普遍對(duì)Chomsky的文法體系存在另外一種描述方式，該方式限制了一般的空串產(chǎn)生式的使用。對(duì)于一般的短語(yǔ)結(jié)構(gòu)文法，G=(∑，V，S，P)：G稱為0型文法，或短語(yǔ)結(jié)構(gòu)文法(PSG)。對(duì)應(yīng)的L(G)叫作0型語(yǔ)言或者短語(yǔ)結(jié)構(gòu)語(yǔ)言(PSL)、遞歸可枚舉集。如果對(duì)于任意

P，均有|

|≥|

|成立，則稱G為1型文法，或上下文有關(guān)文法(CSG)。對(duì)應(yīng)的L(G)叫作1型語(yǔ)言或者上下文有關(guān)語(yǔ)言(CSL)。如果對(duì)于任意

P，均有|

|≥|

|且

V成立，則稱G為2型文法，或上下文無(wú)關(guān)文法(CFG)。對(duì)應(yīng)的L(G)叫作2型語(yǔ)言或者上下文無(wú)關(guān)語(yǔ)言(CFL)。如果對(duì)于任意

P，

均具有形式A

w,A

wB,其中，A,B

V,w

T+，則稱G為3型文法，也可稱為正則文法(RG)或正規(guī)文法。對(duì)應(yīng)的L(G)叫作3型語(yǔ)言，也可稱為正則語(yǔ)言或正規(guī)語(yǔ)言(RL)。正規(guī)語(yǔ)言類包含于上下文無(wú)關(guān)語(yǔ)言類，上下文無(wú)關(guān)語(yǔ)言類包含于上下文相關(guān)語(yǔ)言類，上下文相關(guān)語(yǔ)言類包含于遞歸可枚舉語(yǔ)言類。這里的包含都是集合的真包含關(guān)系，也就是說(shuō)：存在遞歸可枚舉語(yǔ)言不屬于上下文相關(guān)語(yǔ)言類，存在上下文相關(guān)語(yǔ)言不屬于上下文無(wú)關(guān)語(yǔ)言類，存在上下文無(wú)關(guān)語(yǔ)言不屬于正規(guī)語(yǔ)言類。四類文法和對(duì)應(yīng)的四類語(yǔ)言之間都有包含關(guān)系。

定理4-7L是RL的充要條件是存在一個(gè)文法，該文法產(chǎn)生語(yǔ)言L，并且它的產(chǎn)生式要么是形如A

a的產(chǎn)生式，要么是形如A

aB

的產(chǎn)生式，其中A、B為語(yǔ)法變量，a為終極符號(hào)。證明：參考定理2-15的證明。定義4-8線性文法的定義。設(shè)文法G=(∑，V，S，P)。如果對(duì)于

P，

均具有如下形式：A

w,A

wBx，其中，A,B

V,w,x

T*，則稱G為線性文法。對(duì)應(yīng)地，L(G)叫作線性語(yǔ)言。設(shè)文法G=(∑，V，S，P)。如果對(duì)于

P，

均具有如下形式：A

w,A

wB，其中，A,B

V,w

T+，則稱G為右線性文法。對(duì)應(yīng)地，L(G)叫作右線性語(yǔ)言。設(shè)文法G=(∑，V，S，P)。如果對(duì)于

P，

均具有如下形式：A

w,A

Bw，其中，A,B

V,w

T+，則稱G為左線性文法。對(duì)應(yīng)地，L(G)叫作左線性語(yǔ)言。定理4-9L是一個(gè)左線性語(yǔ)言的充要條件是存在文法G，G中的產(chǎn)生式要么是形如A

a的產(chǎn)生式，要么是形如A

Ba

的產(chǎn)生式，且L(G)=L。其中A、B為語(yǔ)法變量，a為終極符號(hào)。證明：讀者自行完成。定理4-10左線性文法與右線性文法等價(jià)。證明：讀者自行完成。結(jié)論：對(duì)于任意右線性文法G，能夠構(gòu)造出對(duì)應(yīng)的左線性文法G’，使得L(G’)=L(G)。對(duì)于任意左線性文法G，能夠構(gòu)造出對(duì)應(yīng)的右線性文法G’，使得L(G’)=L(G)。定義：形如A

的產(chǎn)生式叫作空產(chǎn)生式，也可叫作

產(chǎn)生式。根據(jù)文法分類的定義，在RG,CFG,CSG中，都不能含有空產(chǎn)生式，所以任何CSL中都不包含空語(yǔ)句

?？照Z(yǔ)句

在一個(gè)語(yǔ)言中的存在并不影響該語(yǔ)言有窮描述的存在，因?yàn)槌藶樯煽照Z(yǔ)句

外，空產(chǎn)生式可以不被用于語(yǔ)言中其他任何句子的推導(dǎo)中。當(dāng)允許CSL,CFL,RL包含空語(yǔ)句后，還會(huì)為問(wèn)題的處理提供一些方便。假設(shè)允許RG,CFG,CSG中含有空產(chǎn)生式，也就允許CSL,CFL,RL中包含空語(yǔ)句

?？照Z(yǔ)句不影響文法的類型。定義4-11設(shè)G=(V,T,P,S)為一個(gè)文法，如果S不出現(xiàn)在任何產(chǎn)生式的右部，則(1)如果G是CSG，則仍然稱G=(V,T,P∪{S

},S)為CSG；G產(chǎn)生的語(yǔ)言仍然稱為CSL。(2)如果G是CFG，則仍然稱G=(V,T,P∪{S

},S)為CFG；G產(chǎn)生的語(yǔ)言仍然稱為CFL。(3)如果G是RG，則仍然稱G=(V,T,P∪{S

},S)為RG；G產(chǎn)生的語(yǔ)言仍然稱為RL。限制條件“S不出現(xiàn)在任何產(chǎn)生式的右部”的作用是什么呢？設(shè)正則文法G：S

ab|aS，那么L(G)={a+b}。加入S

后，L(G’)={a+b,

,a}。不僅產(chǎn)生了空語(yǔ)句

，還產(chǎn)生了語(yǔ)句a。定理4-12設(shè)G=(∑，V，S，P)為一個(gè)文法，則存在與G同類型的文法G’=(∑’,V’,S’P’)，使得L(G)=L(G’)，但G’的開(kāi)始符號(hào)S’不出現(xiàn)在G’的任何產(chǎn)生式的右部。

證明：先根據(jù)G構(gòu)造滿足條件的G’，然后證明兩者等價(jià)。取G’=(∑，V∪{S’},S’,P’)，其中P’=P∪{S’

|S

P}，G’與G有相同的類型。如果S不出現(xiàn)在P中任何產(chǎn)生式的右邊，那么效果相當(dāng)于僅僅用S’代換S，P’中產(chǎn)生式實(shí)際上與P中完全相同。先證L(G’)

L(G)。對(duì)

x

L(G’)，在G’中存在如下推導(dǎo)：S’

x，那么在G中存在如下推導(dǎo)：S

x，故x

L(G)。再證L(G)

L(G’)。對(duì)

x

L(G)，在G中存在如下推導(dǎo)：S

x，那么在G’中存在如下推導(dǎo)：S’

x，故x

L(G)。綜上所述，L(G)=L(G’)。結(jié)論：加入空語(yǔ)句不影響語(yǔ)言的類型定理4-13下列命題成立(1)如果L是CSL，則L∪{

}仍然是CSL。(2)如果L是CFL，則L∪{

}仍然是CFL。(3)如果L是RL，則L∪{

}仍然是RL。證明：證明第(1)個(gè)定理，(2)(3)同理可證。設(shè)L是CSL，則存在一個(gè)CSG=(∑，V，S，P)，使得L(G)=L。由前面的預(yù)備定理，不妨設(shè)S不出現(xiàn)在G的任何產(chǎn)生式的右部。取G’=(∑,V,S,P∪{S

})，則G’也是CSG。由于S不出現(xiàn)在G中任何產(chǎn)生式的右部，所以S

不可能出現(xiàn)在任何長(zhǎng)度不為0的句子的推導(dǎo)中，因此L(G’)=L(G)∪{

}。因此L(G)∪{

}是CSL。證畢。結(jié)論：去掉空語(yǔ)句不影響語(yǔ)言的類型。定理4-14下列命題成立(1)如果L是CSL，則L-{

}仍然是CSL。(2)如果L是CFL，則L-{

}仍然是CFL。(3)如果L是RL，則L-{

}仍然是RL。證明：證明第(1)個(gè)定理，(2)(3)同理可證。設(shè)L是CSL，則存在一個(gè)CSG=(∑，V，S，P)，使得L(G)=L。如果

L，則L-{

}=L，所以L-{

}仍然是CSL。由前面的定理，不妨設(shè)S不出現(xiàn)在G的任何產(chǎn)生式的右部。取G’=(V,T,P-{S

},S)，則G’也是CSG。由于S不出現(xiàn)在G中任何產(chǎn)生式的右部，所以S

不可能出現(xiàn)在任何長(zhǎng)度不為0的句子的推導(dǎo)中，因此L(G’)=L(G)-{

}。因此L(G)-{

}是CSL。證畢。4.3語(yǔ)言之間的運(yùn)算及運(yùn)算的封閉性產(chǎn)生復(fù)雜語(yǔ)言的方法之一是對(duì)簡(jiǎn)單的語(yǔ)言進(jìn)行語(yǔ)言的運(yùn)算。

4.3.1語(yǔ)言之間的基本運(yùn)算定義4-15語(yǔ)言的運(yùn)算的定義若語(yǔ)言L1和L2是同一字母表∑上的兩個(gè)語(yǔ)言，定義語(yǔ)言L1和L2的聯(lián)合運(yùn)算為：

L1UL2={w|w∈L1或者w∈L2}語(yǔ)言L1和L2的連接運(yùn)算為：

L1L2={w|w=w1w2，w1∈L1，w2∈L2}語(yǔ)言L1的迭代運(yùn)算（或者星運(yùn)算，閉包運(yùn)算）為：

L1*={w|w=w1w2w3…wm，

wi∈L1，m≥0}=UL1n

對(duì)n≥0

其中：

L10={ε}L11=L1L1n+1=L1L1n

對(duì)n≥1注意:語(yǔ)言L1={an|n>0}，L2={bn|n>0}，則L1L2是{anbm|n,m>0}；而不是是{anbn|n>0}。封閉性：如果任意的、屬于某一語(yǔ)言類的語(yǔ)言在某一特定運(yùn)算下所得到的結(jié)果仍然是該類語(yǔ)言，則稱該語(yǔ)言類對(duì)此運(yùn)算具有封閉性(closureproperty)。有效封閉性：給定一個(gè)語(yǔ)言類的若干個(gè)語(yǔ)言的描述。如果存在一個(gè)算法，它可以構(gòu)造出這些語(yǔ)言在給定運(yùn)算下所獲得的運(yùn)算結(jié)果的相應(yīng)形式的語(yǔ)言描述，則稱此語(yǔ)言類對(duì)相應(yīng)的運(yùn)算是有效封閉的，并稱此語(yǔ)言類對(duì)相應(yīng)的運(yùn)算具有有效封閉性(validclosureproperty)。語(yǔ)言的封閉性可以用于證明某些語(yǔ)言屬于某類語(yǔ)言，以及可以從簡(jiǎn)單的某類語(yǔ)言構(gòu)造復(fù)雜的某類語(yǔ)言。4.3.2語(yǔ)言之間的運(yùn)算的封閉性定義4-16語(yǔ)言的對(duì)運(yùn)算的封閉定義給定字母表∑，Ψ是∑上的一類語(yǔ)言，語(yǔ)言L1，L2СΨ，令α是語(yǔ)言上的二元運(yùn)算：(L1，L2)→α(L1，L2)；β是語(yǔ)言上的一元運(yùn)算：L1→β(L1)；若對(duì)于Ψ的任意語(yǔ)言L1和L2，α(L1，L2)也是Ψ的語(yǔ)言，則稱Ψ對(duì)于運(yùn)算α是封閉的；若對(duì)于Ψ的任意語(yǔ)言L1，β(L1)也是Ψ的語(yǔ)言，則稱Ψ對(duì)于運(yùn)算β是封閉的。定理4-17每個(gè)i（i=0，1，2，3）型語(yǔ)言對(duì)聯(lián)合，連接和迭代運(yùn)算是封閉的。證明：

已知同一字母表∑上的語(yǔ)言L1和L2，產(chǎn)生L1的文法G1=（∑，V1，S1，P1），產(chǎn)生L2的文法G2=（∑，V2，S2，P2），假定V1∩V2=Ф，S！∈V1，S！∈V2，設(shè)置V=V1UV2U{S}。對(duì)于聯(lián)合運(yùn)算：構(gòu)造G3=（∑，V，S，P3），其中P3={S→S1}U{S→S2}UP1UP2，對(duì)于i=0，1，2，若G1和G2是i型文法，則G3也是；從S開(kāi)始，使用S→S1，得到L(G1)，或者使用S→S2，得到L(G2)，顯然，L(G3)=L(G1)UL(G2)，所以，對(duì)于i=0，1，2，Ψi對(duì)于聯(lián)合封閉。如果G1和G2是右線性文法，則G3不是，構(gòu)造文法G4=（∑，V，S，P4），其中P4為：

{S→w1|S1→w1在P1中}U{S→w2|S2→w2在P2中}UP1UP2；則G4是右線性文法，且L(G4)=L(G1)UL(G2)。對(duì)于連接運(yùn)算：構(gòu)造G5=（∑，V，S，P5），其中P5={S→S1S2}UP1UP2，若G1和G2是上下文無(wú)關(guān)文法，則G5也是上下文無(wú)關(guān)文法；且S1=>*w1，S2=>*w2，S=>S1S2=>*w1w2，所以L(G5)=L(G1)L(G2)；所以2型語(yǔ)言對(duì)連接封閉。若G1和G2是0型或者1型文法，文法G5可能會(huì)有問(wèn)題，例如：文法G1為：S1→b，文法G2為：S2→c，bS2→bb；則L(G1)=，L(G2)={c}；L1L2={bc}；而對(duì)于，S=>S1S2=>bS2=>bc；或S=>S1S2=>bS2=>bb；即文法G5產(chǎn)生的語(yǔ)言為{bc,bb}，它不是語(yǔ)言L1和L2的連接。該問(wèn)題產(chǎn)生的原因是S1和S2產(chǎn)生的串發(fā)生了串道，即S1產(chǎn)生的串可能將S2產(chǎn)生的串作為下文，S2產(chǎn)生的串可能將S1產(chǎn)生的串作為上文；為解決這個(gè)問(wèn)題，將∑復(fù)制為∑′和∑″，令∑′={x′|x∈∑}，∑″={x″|x∈∑}，將P1中的x用相應(yīng)的x′代替，得到P′，將P2中的x用相應(yīng)的x″代替，得到P″，構(gòu)造G6=（∑，VU∑′U∑″，S，P6），其中P6為：{S→S1S2}UP1′UP2″U{x′→x|x∈∑}U{x″→x|x∈∑}則L(G6)=L(G1)L(G2)；所以0型和1型語(yǔ)言對(duì)連接封閉。對(duì)于右線性文法，S→S1S2不適應(yīng)，構(gòu)造G7=（∑，V，S1，P7），其中P7為：{A→bB|A→bB在P1中}U{A→bS2|A→b在P1中}（注意：若P1中有空串產(chǎn)生式，則要先消除空串產(chǎn)生式）L(G7)=L(G1)L(G2)；所以3型語(yǔ)言對(duì)連接封閉。對(duì)于迭代運(yùn)算：考慮文法S→ε|S′S′→S1|S1S′則S推導(dǎo)出ε和S1n(n≥1)。構(gòu)造G8=（∑，V1U{S，S′}，S，P8），其中P8為：{S→ε|S′}U{S′→S1|S1S′}UP1若G1是上下文無(wú)關(guān)文法，則G8也是上下文無(wú)關(guān)文法；且S=>*L(G1)*，所以2型語(yǔ)言對(duì)迭代封閉。若G1是0型或者1型文法，文法G8會(huì)有同樣的串道問(wèn)題。首先,消除G1中的空串產(chǎn)生式，將∑復(fù)制為∑′和∑″,令∑′={x′|x∈∑}，∑″={x″|x∈∑}，將P1中的x用相應(yīng)的x′代替,得到P1′,將P1中的x用相應(yīng)的x″代替，得到P1″，構(gòu)造G1′=（∑，V1U∑′U{S1}，S1，P1′）；G1″=（∑，V1U∑″U{S2}，S2，P1″）；構(gòu)造G9=（∑，V1U∑′U∑″U{S，S1，S1′，S2，S2′}，S，P9）；其中P9為：{S→ε|S1′|S2′}U{S1′→S1|S1S2′}U{S2′→S2|S2S1′}UP1′UP1″U{x′→x|x∈∑}U{x″→x|x∈∑}；則L(G9)=L(G1)*；所以0型和1型語(yǔ)言對(duì)迭代封閉。對(duì)于右線性文法，引入新的開(kāi)始符號(hào)S和S→ε來(lái)產(chǎn)生空串ε（若在P1中有S1→ε，則刪除S1→ε），增加S→w（其中w是P1中的S1→w），以便開(kāi)始推導(dǎo)，然后，對(duì)于每個(gè)形如A→b的產(chǎn)生式，增加A→bS（不刪除A→b），這樣，從S開(kāi)始，可以推導(dǎo)出形如w1w2…wj′A的串，其中：w1，w2，…，wj=wj′b都在L1中，我們可以在推導(dǎo)出w1w2…wj時(shí)停止，也可以從w1w2…wjS開(kāi)始推導(dǎo)出另一個(gè)更長(zhǎng)的串，直至L(G1)*；所以，若G1是右線性文法，則G=（∑，V1U{S}，S，P10），其中P10為：{S→ε}U（P-{S1→ε}）U{A→bS|若A→b在P1中}U{S→w|S1→wP1中}也是右線性的文法，且L(G10)=L(G1)*；所以3型語(yǔ)言對(duì)迭代封閉。證畢。定理4-18右線性語(yǔ)言對(duì)于補(bǔ)和交運(yùn)算是封閉的。證明：該定理的證明需要使用自動(dòng)機(jī)的知識(shí)，留待今后證明。定理4-19上下文無(wú)關(guān)語(yǔ)言對(duì)于補(bǔ)和交運(yùn)算不是封閉的。證明：舉一個(gè)反例即可。上下文無(wú)關(guān)語(yǔ)言L1={anbncm|n,m>0}；上下文無(wú)關(guān)語(yǔ)言L2={aibkck|i,k>0}它們的交集為L(zhǎng)={anbncn|n>0},而該語(yǔ)言不是上下文無(wú)關(guān)語(yǔ)言，是一個(gè)上下文相關(guān)語(yǔ)言。證畢。對(duì)于語(yǔ)言，還有一個(gè)有用的運(yùn)算-----置換。

定義4-20置換的定義一個(gè)映射g：∑*→Y*(∑和Y是兩個(gè)字母表)，若g(ε)={ε}，且對(duì)n≥1；g(w1w2…wn)=g(w1)g(w2)…g(wn)；則g是一個(gè)置換映射。特別地，若g(a)只包含Y*的一個(gè)元素，則g稱為同態(tài)。直觀上看，同態(tài)僅僅只改變了構(gòu)成串的成分的名字，除非同態(tài)把元素a映射成為ε或則是一個(gè)串。若L是字母表∑上的一個(gè)語(yǔ)言，則g(L)=Ug(w)，其中w∈L。且g(a*)=g(a)g(a)…g(a)=(g(a))*。例4-21∑={a，b}，g(a)=0*，g(b)=1；若語(yǔ)言L=(aba)*，則g(L)=(0*10*)*。定理4-22上下文無(wú)關(guān)語(yǔ)言對(duì)于（上下文無(wú)關(guān)）置換映射是封閉的。證明：上下文無(wú)關(guān)文法G=（∑，V，S，P），產(chǎn)生無(wú)關(guān)語(yǔ)言L，g是一個(gè)置換映射：g(x)=L∑，其中x∈∑，將文法G改造為G′=（Y，VU∑′，S，P′）；方法是將G中的每個(gè)產(chǎn)生式的右邊的終結(jié)符x替換為x′，增加產(chǎn)生式某些產(chǎn)生式，使得x′=>+L∑，文法G產(chǎn)生串x1x2…xn，而文法G′產(chǎn)生串x1′x2′…xn′，再得到串L∑1L∑2…L∑n。所以文法G′產(chǎn)生語(yǔ)言g(L)，也是上下文無(wú)關(guān)的語(yǔ)言。證畢。定理4-23右線性語(yǔ)言對(duì)于（上下文無(wú)關(guān)）置換映射是封閉的。證明：類似上下文無(wú)關(guān)語(yǔ)言的證明，略。4.4正則表達(dá)式和正則集計(jì)算學(xué)科討論的是什么能夠被有效地自動(dòng)化，而實(shí)現(xiàn)有效自動(dòng)化的基礎(chǔ)首先是實(shí)現(xiàn)對(duì)問(wèn)題恰當(dāng)?shù)男问交枋?。在形式語(yǔ)言中，有時(shí)使用表達(dá)式的形式來(lái)代表一個(gè)語(yǔ)言。對(duì)于正則的語(yǔ)言，可以使用正則表達(dá)式來(lái)表示；正則表達(dá)式對(duì)正則語(yǔ)言的表示具有特殊的優(yōu)勢(shì)：它更簡(jiǎn)單，更方便，更容易進(jìn)行處理；而且，這種表達(dá)形式還更接近語(yǔ)言的集合表示和語(yǔ)言的計(jì)算機(jī)表示。語(yǔ)言的集合表示形式使得它本身更容理解和使用；而適合計(jì)算機(jī)的表示形式又使得它更容易被計(jì)算機(jī)系統(tǒng)處理。本節(jié)介紹正則的表達(dá)式和它表示的正則集。定義4-24正則集的定義L是字母表∑上的語(yǔ)言，若語(yǔ)言L是有限的，則語(yǔ)言L是正則的；或者語(yǔ)言L能夠由下列運(yùn)算遞歸地產(chǎn)生：若L1和L2是正則的，且L=L1UL2；若L1和L2是正則的，且L=L1L2；若L1是正則的，且L=L1*；則L也是正則的。若一個(gè)語(yǔ)言是正則，該語(yǔ)言也叫作正則集。例如，下列語(yǔ)言是正則的：空集φ和空串的集合{ε}，因?yàn)樗鼈兪怯邢薜?；語(yǔ)言{ab，a}*也是正則的，因?yàn)槭钦齽t的語(yǔ)言經(jīng)過(guò)運(yùn)算得到的。定義4-25正則表達(dá)式的定義正則表達(dá)式R和它所表達(dá)的正則集S(R)的定義φ是一個(gè)正則表達(dá)式，S(φ)=φ；ε是一個(gè)正則表達(dá)式，S(ε)={ε}；若a∈∑，則a是一個(gè)正則表達(dá)式，S(a)={a}；若R1和R2是正則表達(dá)式，則R1+R2是正則表達(dá)式，S(R1+R2)=S(R1)US(R2)若R1和R2是正則表達(dá)式，則R1R2是正則表達(dá)式，S(R1R2)=S(R