[政史地]第2節(jié)課第二章-wenkub
2022-10-29 07:21:39 本頁面
【正文】 ，用于產(chǎn)生所要描述的語言的全部句子 (可無限多 )，這些規(guī)則構(gòu)成了該語言的 文法 。 符號串 用字母表中的符號所組成的任何有限 序列。 顯然， | ? |= 0。 注意，一般說來， xy 不等于 yx； 但 ?x = x? = x 方冪 符號串 x與其自身的 n1次連接稱為 x 的 n 次方冪，記為： nx????? ?011:,......3,2xnxxxxx nn我們約定這里即 符號串集合的和與積 設(shè) A， B為兩個符號串集合，定義： 和： A+B（或 A∪ B） ={w | w?A，或 w?B } 例如，若 A={a,b,c}， B={00,11}，則 A+B={a,b,c,00,11}。 ? 我們以幾個英語句子構(gòu)成的語言為例進行討論。 ? 語法規(guī)則也稱為 產(chǎn)生式 (Production)。例如， ? 首先用規(guī)則①進行第一步推導(dǎo) (derivation)，就可得到 主語短語 動詞短語 ， 記為： 句子 ? 主語短語 動詞短語 ? 所得的符號串含有兩個 語法范疇 ，可對其中任一個 (如對 動詞短語 )進行新的 推導(dǎo) （替換）： 句子 ? 主語短語 動詞短語 ? 主語短語 動詞 賓語短語 ? 重復(fù)上述過程，可得到一個推導(dǎo)序列： 推導(dǎo) 所用 所得的符號串 步驟 規(guī)則 1 ① 句子 ? 主語短語 動詞短語 2 ③ ? 主語短語 動詞 賓語短語 3 ② ? the 名詞 動詞 賓語短語 4 ④ ? the 名詞 動詞 冠詞 名詞 5 ⑤ ? the monkey 動詞 冠詞 名詞 6 ⑦ ? the monkey eat 冠詞 名詞 7 ⑩ ? the monkey eat a 名詞 8 ⑥ ? the monkey eat a banana ? 從前面的推導(dǎo)看，從 句子 出發(fā)，經(jīng) 8步推導(dǎo)得到了一個英語句子。如 名詞 、 動詞 、 冠詞 的定義規(guī)則可簡記為： ? 名詞 ::= monkey | banana ? 動詞 ::= eat | has ? 冠詞 ::= the | a 語法規(guī)則及其產(chǎn)生的語言 ? 前面的語法規(guī)則可以產(chǎn)生 16個不同的句子， 由這 16個句子組成的集合，就是該規(guī)則所定義（或所產(chǎn)生）的 語言 。 ? 由這些非終結(jié)符號組成的集合稱為 非終結(jié)符號集 ，用 VN 記之。為文產(chǎn)生式集終結(jié)符集分別稱為非終結(jié)符集空有限集為非。 ? ?? ? ??????????? ? ?????????????GGTNUPUVUVSPVVS??????????或的直接推導(dǎo)記為是我們把通常。則稱為長度為對于步推導(dǎo)稱為對于情況使上的符號串序列存在或如果產(chǎn)生的推導(dǎo)是符號串，稱上的兩個是為一文法設(shè)定義??。是則稱若是文法設(shè)定義),(,][***GVGSVSGTG????????例 ： G[S]: S → aB | Bb B → a | b 該文法僅有 6個句型 S, aB, Bb, aa, ab, bb， 僅有 3個句子 aa, ab, bb 。當(dāng)語言是無限集時，能否用有限的規(guī)則來描述呢？回答是肯定的 , 只需使用文法的 遞歸定義 即可。歸的非終結(jié)符一文法至少含有一個遞遞歸的非終結(jié)符號。 例如，由奇數(shù)個 a的符號串構(gòu)成的語言 L可由文法 G3 = ( {S}, {a}, {S?aSa|a}, S ) 或 G
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1