[政史地]第2節(jié)課第二章(完整版)
【正文】 A+B={a,b,c,00,11}。 ? 語法規(guī)則也稱為 產(chǎn)生式 (Production)。如 名詞 、 動詞 、 冠詞 的定義規(guī)則可簡記為： ? 名詞 ::= monkey | banana ? 動詞 ::= eat | has ? 冠詞 ::= the | a 語法規(guī)則及其產(chǎn)生的語言 ? 前面的語法規(guī)則可以產(chǎn)生 16個不同的句子， 由這 16個句子組成的集合，就是該規(guī)則所定義（或所產(chǎn)生）的 語言 。為文產(chǎn)生式集終結(jié)符集分別稱為非終結(jié)符集空有限集為非。則稱為長度為對于步推導(dǎo)稱為對于情況使上的符號串序列存在或如果產(chǎn)生的推導(dǎo)是符號串，稱上的兩個是為一文法設(shè)定義??。當(dāng)語言是無限集時，能否用有限的規(guī)則來描述呢？回答是肯定的 , 只需使用文法的 遞歸定義 即可。 例如，由奇數(shù)個 a的符號串構(gòu)成的語言 L可由文法 G3 = ( {S}, {a}, {S?aSa|a}, S ) 或 G4 = ( {S,A}, {a}, {S?aA|a, A?aS}, S ) 產(chǎn)生，即 L(G3) = L(G4) = L 例如，由奇數(shù)個 a的符號串構(gòu)成的語言 L可由文法 G3 = ( {S}, {a}, {S?aSa|a}, S ) 或 G4 = ( {S,A}, {a}, {S?aA|a, A?aS}, S ) 產(chǎn)生，即 L(G3) = L(G4) = L )()(,212121GLGLGGGG?當(dāng)且僅當(dāng)?shù)葍r的是和稱是兩個文法和設(shè)定義例 設(shè) ?={a,b}, 則產(chǎn)生語言 A的文法如下： (1) A→aBa B→b|Bb (2) A→aBa B→b|bB (3) A→aB B→ba|bB (4) A→aB B→bC C→bC|a }1{ ?? naabA n。 文法 G2[E]： E ? E+T | T T ? T*F | F F ? (E) | i 顯然， G2是遞歸定義的。是則稱若是文法設(shè)定義),(,][***GVGSVSGTG????????例 ： G[A]: A → Bb B → a 該文法僅有 3個句型 A, Bb, ab， 僅有 1個句子 ab 。,][][12注 ： 為使用上的方便，我們用 ‘ ?’ 代替產(chǎn)生式中的 ‘ ::=’。 ? 然而，若不考慮 語義 ，則我們就必須承認(rèn)它們是語法上 合法 的句子。 ? 推導(dǎo) 從語言最大的一個 語法范疇 （本例中是 句子 ）開始，反復(fù)用語法規(guī)則中? ::=” 右側(cè)的符號串取代其左側(cè)符號，直到所得的符號串中不再含有可被替換的 語法范疇 。 符號串集合的閉包 根據(jù)符號串集合的和運(yùn)算，我們又可分別定義符 號串集合 A的 正閉包 A+ 及 自反傳遞閉包 A* 如下： ??? ????????? niiAAAAAA21:)( 閉包正的傳遞???????? AAAAAii}{}{:0*?? ??的自反傳遞閉包例如，若 A={a,b}，則 },{?bbbbbababbaaabbabaaabaaabbbaabaabaA ??},{*?bbbbbababbaaabbabaaabaaabbbaabaabaA ????? ????????? nii AAAAA 21???????? AAAAii }{}{
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1