【正文】 ?例： 文法 G[S]： S CD Ab bA C aCA Ba aB C bCB Bb bB AD aD C ε BD bD D ε Aa bD L(G)={w|w∈ {a,b}*} 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?有些定義中，將上下文有關(guān)文法的產(chǎn)生式的形式描述為 α1Aα2 α1βα2，其中 α α2和 β都在 V*中， β≠ε， A在 VN中 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 α β均滿足： α是 一個(gè) 非終結(jié)符， β∈ V*，則文法 G是 2型文法 （ 上下文無(wú)關(guān)文法 ） 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?有時(shí)將 2型文法的產(chǎn)生式表示為 A β的形式，其中 A∈ VN，也就是用 β取代非終結(jié)符 A時(shí)，與 A所在的上下 文無(wú)關(guān)，因此取名為 上下文無(wú)關(guān) ?例 、 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 ： 文法 G[S]： S aB|bA A a|aS|bAA B b|bS|aBB 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 A αB或 A α，其中 A和 B都是非終結(jié)符， α∈ VT*，則文法 G是 3型文法 （ 正規(guī)文法 ） ?例 ：文法 G[S]： S 0A|1B|0 A 0A|1B|0S B 1B|1|0 你會(huì)忘記我嗎？ 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?4個(gè)文法類的定義是 逐漸增加限制 的，因此，每一種正規(guī) 文法都是上下文無(wú)關(guān)的，每一種上下文無(wú)關(guān)文法都是上 下文有關(guān)的，而每一種上下文有關(guān)文法都是 0型文法 ?稱 0型文法產(chǎn)生的語(yǔ)言為 0型語(yǔ)言，上下文有關(guān)文法、上 下文無(wú)關(guān)文法和正規(guī)文法產(chǎn)生的語(yǔ)言分別稱為上下文有 關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。即 A t,其中 t∈ VT* * + 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 二 .上下文無(wú)關(guān)文法中的 ε規(guī)則 ?ε規(guī)則：形如 A ε的產(chǎn)生式，其中 A∈ VN ?某些著作和講義中限制這種規(guī)則的出現(xiàn)。 ⑵ 給出語(yǔ)言描述，構(gòu)造文法。但可以為無(wú)二義性尋找一組充分條件 ?二義文法改造為無(wú)二義文法 例 ： G[E]： E T|E+T G[E]: E i T F|T*F E E+E F （ E） |i E E*E 規(guī)定優(yōu)先順序和結(jié)合律 E (E) 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 (2). | a x | = | x a | = | x | + 1 ( a ∈ ∑ ) 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 3. 符號(hào)串的連結(jié)： 設(shè) x 與 y 是字母表 ? 上的兩個(gè)符號(hào)串， 把 y 的所有符號(hào)相繼寫(xiě)在 x 的符號(hào)之后所得到的符號(hào)串 稱為 x 與 y 的連結(jié)，用 x y 表示 注意 : ? | x y | = | x | + | y | ? ? x = x ? = x ? x y ≠ y x ( 一般說(shuō)來(lái) ) 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 4 .符號(hào)串的逆： 設(shè) x 是字母表 ? 上的符號(hào)串，其逆為符號(hào)串 x 的倒置， 記為 。 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ： 設(shè) x 是字母表 ? 上的符號(hào)串，則 x 的冪運(yùn)算 為 x 0 = ? x 1=x x 2=xx ?????? x n=x n1x (xx n1) 例 : 若 x = ab 則 : x 0 = ?, x 1 = ab, x 2 = abab, ??????, x n = abab??? ab 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ： 設(shè) A 是符號(hào)串集合，則符號(hào)串 A 的冪運(yùn) 算為： A0={?} A1=A A2=AA ?????? An=A n1A (AA n1) 例 : 若 A = { ab, cd } 則 : A 0 = { ? }, A 1 = { ab, cd }, A 2 = { abab, abcd, cdab, cdcd }, ?????? 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 注意 : ?A*=A0∪ A+ ?A+=AA*=A*A 若 A = { a, b } 則 : A*= {?, a, b, aa, ab, ba, bb, aaa, ??? } A+= {a, b, aa, ab, ba, bb, aaa, ??? } A的閉包與正閉包： 正閉包表示為 A+ ， 集合 A 的閉包表示為 A* ， A UA UA UA A K1K32 1 U ?? ????? A UA UA UUA A A K0K32 10* U ??????盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。一個(gè)句型的 最左 直接短語(yǔ) 稱為該句型的 句柄 * + 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 G[E]: E T|E+T T F|T*F F （ E） |i 句型 i*i+i ?短語(yǔ)：