[政史地]第2節(jié)課第二章-預(yù)覽頁
【正文】 〈 數(shù)字 〉 → 0 | 1 | 2 | … | 9 （ 3）建立一種 裝置（算法或過程） ， 它以某字母表上的符號串為輸入，判別該符號串是否為所描述語言的句子。 符號串的長度 = 符號串中所含符號的個數(shù)。 本課約定 用 A、 B、 C、 ?等表示字母表或 符號串集； 用 a,b,c,S,T,U 等表示符號； 用 s,t,u,x,y,z,?,?,? 等表示符號串。 積： A?B（或 AB） = { xy | x?A, 且 y?B } 例如，若 A={a,b,c}， B={00,11}，則 AB={a00,a11,b00,b11,c00,c11} 顯然， A+? = ?+A = A ； A? = ?A = ? ； {?}A = A{?} = A 符號串集合的方冪 )0(}{:,110 ???? ?? nAAAAAAAAnnn?的方冪定義是符號串集合設(shè)例如，若 A={a,b}，則 },{},{},{}{3210b b bb b ab a bb a aa b ba b aa a ba a aAbbbaabaaAbaAA???? ?7。并設(shè)每個句子都是?主 謂 賓?結(jié)構(gòu)。 ① 句子 ::=主語短語 動詞短語 ② 主語短語 ::= the 名詞 ① 句子 ::=主語短語 動詞短語 ② 主語短語 ::= the 名詞 ③ 動詞短語 ::=動詞 賓語短語 ④ 賓語短語 ::=冠詞 名詞 ⑤ 名詞 ::=monkey ⑥ 名詞 ::=banana ⑦ 動詞 ::=eat ⑧ 動詞 ::=has ⑨ 冠詞 ::= the ⑩ 冠詞 ::= a ? 現(xiàn)在討論如何用上述規(guī)則 推導(dǎo) 出相應(yīng)語言的全部 句子 。故前面的推導(dǎo)稱為 長度為 8的推導(dǎo) 。 ? 應(yīng)指出，所產(chǎn)生的句子中，有些句子的含義是荒謬 的（如 the banana eat a monkey 和 the banana eat the banana 等 ）。對于上例，我們有： VN = {〈 句子 〉 ,〈 主語短語 〉 ,〈 動詞短語 〉 , 〈 賓語短語 〉 ,〈 名詞 〉 ,〈 動詞 〉 ,〈 冠詞 〉 } ? 含有若干個基本符號，由于這些基本符號不需要進(jìn)一步定義，故通常將它們稱為 終結(jié)符號 。其中是一四元組一文法定義),(。且其中和可分別寫成當(dāng)且僅當(dāng)，直接產(chǎn)生或的直接推導(dǎo)是稱是一文法設(shè)定義,)(,][22**當(dāng)然，上述定義中的 ?、 ?、 ?都可以是空串 ?。產(chǎn)生的句子是則稱特別地，當(dāng)句型的一個句型。 上的。 例 ： G[A]: A→Bb B→a 例 ： G[S]: S→aB|Bb B→a|b }{])[( abAGL ?},{])[( bbabaaSGL ?例 ： G[S]: S → 0 S1 | 01 S,01,0S1,0011,00S11,000111,000S111,… ,是句 型，其中 01， 0011， 000111,…, 是句子，故 例 ： 設(shè) ?={a,b}, 則 ?+ 字符串集的 BNF表示 如下： G[A]: A → a | b | Aa | Ab }110{])[( ?? nSGL nn所謂 遞歸定義 ， 是 指在定義一個語法成分時，直接或間接地使用了 該 語法成分自身 。右左為遞歸的，稱右左是則稱且若存在推導(dǎo)是直接遞歸的則稱產(chǎn)生式的形式具有若為文法設(shè)定義,)/()/()/(,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1