Chomsky文法体系及语言之间的运算课件.ppt

定理4-9L是一個左線性語言的充要條件是存在文法G，G中的產生式要麼是形如A?a的產生式，要麼是形如A?Ba的產生式，且L(G)=L。其中A、B為語法變數，a為終極符號。證明：讀者自行完成。定理4-10左線性文法與右線性文法等價。證明：讀者自行完成。結論：對於任意右線性文法G，能夠構造出對應的左線性文法G’，使得L(G’)=L(G)。對於任意左線性文法G，能夠構造出對應的右線性文法G’，使得L(G’)=L(G)。定義：形如A??的產生式叫作空產生式，也可叫作?產生式。根據文法分類的定義，在RG,CFG,CSG中，都不能含有空產生式，所以任何CSL中都不包含空語句?。空語句?在一個語言中的存在並不影響該語言有窮描述的存在，因為除了為生成空語句?外，空產生式可以不被用於語言中其他任何句子的推導中。當允許CSL,CFL,RL包含空語句後，還會為問題的處理提供一些方便。假設允許RG,CFG,CSG中含有空產生式，也就允許CSL,CFL,RL中包含空語句?。空語句不影響文法的類型。定義4-11設G=(V,T,P,S)為一個文法，如果S不出現在任何產生式的右部，則(1)如果G是CSG，則仍然稱G=(V,T,P∪{S??},S)為CSG；G產生的語言仍然稱為CSL。(2)如果G是CFG，則仍然稱G=(V,T,P∪{S??},S)為CFG；G產生的語言仍然稱為CFL。(3)如果G是RG，則仍然稱G=(V,T,P∪{S??},S)為RG；G產生的語言仍然稱為RL。限制條件“S不出現在任何產生式的右部”的作用是什麼呢？設正則文法G：S?ab|aS，那麼L(G)={a+b}。加入S??後，L(G’)={a+b,?,a}。不僅產生了空語句?，還產生了語句a。定理4-12設G=(∑，V，S，P)為一個文法，則存在與G同類型的文法G’=(∑’,V’,S’P’)，使得L(G)=L(G’)，但G’的開始符號S’不出現在G’的任何產生式的右部。證明：先根據G構造滿足條件的G’，然後證明兩者等價。取G’=(∑，V∪{S’},S’,P’)，其中P’=P∪{S’??|S???P}，G’與G有相同的類型。如果S不出現在P中任何產生式的右邊，那麼效果相當於僅僅用S’代換S，P’中產生式實際上與P中完全相同。先證L(G’)?L(G)。對?x?L(G’)，在G’中存在如下推導：S’???x，那麼在G中存在如下推導：S???x，故x?L(G)。再證L(G)?L(G’)。對?x?L(G)，在G中存在如下推導：S???x，那麼在G’中存在如下推導：S’???x，故x?L(G)。綜上所述，L(G)=L(G’)。結論：加入空語句不影響語言的類型定理4-13下列命題成立(1)如果L是CSL，則L∪{?}仍然是CSL。(2)如果L是CFL，則L∪{?}仍然是CFL。(3)如果L是RL，則L∪{?}仍然是RL。證明：證明第(1)個定理，(2)(3)同理可證。設L是CSL，則存在一個CSG=(∑，V，S，P)，使得L(G)=L。由前面的預備定理，不妨設S不出現在G的任何產生式的右部。取G’=(∑,V,S,P∪{S??})，則G’也是CSG。由於S不出現在G中任何產生式的右部，所以S??不可能出現在任何長度不為0的句子的推導中，因此L(G’)=L(G)∪{?}。因此L(G)∪{?}是CSL。證畢。結論：去掉空語句不影響語言的類型。定理4-14下列命題成立(1)如果L是CSL，則L-{?}仍然是CSL。(2)如果L是CFL，則L-{?}仍然是CFL。(3)如果L是RL，則L-{?}仍然是RL。證明：證明第(1)個定理，(2)(3)同理可證。設L是CSL，則存在一個CSG=(∑，V，S，P)，使得L(G)=L。如果??L，則L-{?}=L，所以L-{?}仍然是CSL。由前面的定理，不妨設S不出現在G的任何產生式的右部。取G’=(V,T,P-{S??},S)，則G’也是CSG。由於S不出現在G中任何產生式的右部，所以S??不可能出現在任何長度不為0的句子的推導中，因此L(G’)=L(G)-{?}。因此L(G)-{?}是CSL。證畢。4.3語言之間的運算及運算的封閉性產生複雜語言的方法之一是對簡單的語言進行語言的運算。4.3.1語言之間的基本運算定義4-15語言的運算的定義若語言L1和L2是同一字母表∑上的兩個語言，定義語言L1和L2的聯合運算為：L1UL2={w|w∈L1或者w∈L2}語言L1和L2的連接運算為：L1L2={w|w=w1w2，w1∈L