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