自然語言理解講義第二章-展示頁
2024-10-28 09:39本頁面
【正文】 ?對規(guī)則形式的約束： – ??? ?， ?是任意串，且 ?的長度小于 ?的長度 – ? A ? ? ? ? ? A是非終結(jié)符， ?、 ?、 ?是任意串 – 以上兩種形式等價 – 敏感：在一定的上下文環(huán)境下 A可改寫為 ? 喬姆斯基 2型文法 ?上下文無關(guān)文法，上下文自由文法 CFG： Context Free Grammar ?對規(guī)則形式的約束： – A?? ： A是非終結(jié)符， ?是任意串 – 在任何上下文環(huán)境下 A可改寫為 ? 上下文無關(guān)文法的一個例子 ?S?aAS ?S?a ?A?SbA ?A?ba S?aAS?aAa?aSbAa?aabAa?aabbaa 喬姆斯基 3型文法 ?正規(guī)文法，正則文法 RG： Regular Grammar ?對規(guī)則形式的約束 – A?Bx或者 A?x， A,B是非終結(jié)符， x是終結(jié)符 ?一部正則文法可以表示為一個正則表達(dá)式 例子： {a{b|c}*}+[d|e]{f|g|h}+ 喬姆斯基層級以外的文法類別 ?介于 CFG和 CSG之間的語法類別 – 索引文法（ IG: Index Grammar） 可以生成 {anbn}形式的語言 – 樹粘接文法 TAG： Tree Adjoining Grammar ?與喬姆斯基語法層級相交叉的語法類別 索引文法 (1) ?索引文法是一個五元組（ VN, VT,VI,P,S) ? VN,VT,S與前面的定義相同 ? VI是索引的有限集合 ? P是重寫規(guī)則的有限集合，規(guī)則形式為： 1) A?? 2) A?B(f) 3) A(f)?? A , B ∈ VN, f ∈ VI, ?∈ (VN∪ VT)* 索引文法 (2) ? 直接推導(dǎo) (?)的定義 –如果 A?X1X2… Xk是規(guī)則集中具有 1)形式的規(guī)則，那么： βA(δ)γ?βX1(δ1) X2(δ2)… Xk(δk)γ 其中， Xi∈ VN時， δi＝ δ； Xi∈ VT時， δi＝ ε –如果 A?B(f)是規(guī)則集中具有 2)形式的規(guī)則，那么βA(δ)γ?βB(fδ) γ –如果 A(f)?X1X2… Xk是規(guī)則集中具有 3)形式的規(guī)則，那么： βA(fδ)γ?βX1(δ1) X2(δ2)… Xk(δk)γ 其中， Xi∈ VN時， δi＝ δ； Xi∈ VT時， δi＝ ε ? 推導(dǎo) (?*)的定義和語言的定義與前面類似 索引文法 (3) ? 例子 （規(guī)則集） S ? S(α) S ? ABC A(α) ? aA B(α) ? bB C(α) ? cC A ? a B ? b C ? c ? 推導(dǎo) S?S(α) ?S(αα) ?S(ααα) ?A(ααα)B(ααα)C(ααα) ?aA(αα)B(ααα)C(ααα) ?aaA(α)B(ααα)C(ααα) ?aaaaB(ααα)C(ααα) ?…… ?aaaabbbbcccc ?可以生成 {anbn}形式的語言，不是 CFG 其他文法 ?鏈文法（ Link Grammar） ?依存文法（ Dependency Grammar） ?范疇文法（ CategorialGrammar） 范疇文法 (1) ? Montague,1970。 V+ =V*{?}。自然語言理解講義 第二章 句法與句法分析 (1): 形式語言與自動機
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1