自然語言理解講義第二章(已修改)
2024-10-31 09:39 本頁面
【正文】 自然語言理解講義 第二章 句法與句法分析 (1): 形式語言與自動機 內(nèi)容提要 ?如何描述語言 ?形式文法定義 ?喬姆斯基的文法層級 ?索引文法 ?范疇文法 ?自動機 ?文法判定的復雜度 ?用形式文法描述自然語言 ?文法、語言與自動機的關系 如何描述一種語言 ?枚舉 – 給出語言中的所有句子 – 對于含無限多個句子的語言不合適 ?文法 (語法 ) – 給出生成語言中所有句子的方法 – 當且僅當能夠用該方法產(chǎn)生的句子才屬于該語言 ?自動機 – 給出識別該語言中句子的機械方法 形式文法 (1) ? 形式文法：四元組 G = VT, VN, S, P ? 終結符（ Terminals）的有限集合 VT – 終結符是句子中實際出現(xiàn)的符號 – 相當于單詞表（有時也稱為字母表） ? 非終結符（ Nonterminals）的有限集合 VN – 非終結符在句子中不實際出現(xiàn) – 但在推導中起變量作用 – 相當于語言中的語法范疇 形式文法 (2) ? 起始符 S – S屬于 VN – 相當于句法范疇中的句子 ? 重寫式規(guī)則 (Rewriting Rules)的有限集合 P或 產(chǎn)生式規(guī)則 (Production Rules)的有限集合 P – 基本形式： ??? – 含義：將 ?改寫成 ? – ?和 ?是終結符和非終結符組成的串 – ?非空， ?可以為空 (?) 形式文法 (3) ?定義 V*=(VN?VT)*， ??V*。 V*是 VN和 VT上的任意字符串，包括空串 (?)。 V+ =V*{?}。 ?直接推導： ? x ??? y ? 如果 x?y是 P中的一條規(guī)則 ?推導： ? ?* ? 如果 ?可以經(jīng)過多次直接推導得到 ? ?語言： L(G)={? | ?∈ VT*； S ?* ?} G?一個例子 例 ：設形式文法 G的 VT={the, John, ate, apple}， VN={S, NP, VP, ART, N, V, NAME}, P={1. S?NP VP, 2. VP?V NP, 3. NP?NAME, 4. NP?ART N, 5. NAME?John, 6. V?ate, 7. ART?the, 8. N?cat}，其中 NP代表名詞短語、VP代表動詞短語等等。則句子 “ John ate the apple”的生成過程如下 S?NP VP (重寫 S) ? NAME VP (重寫 NP) ? John VP (重寫 NAME) ? John V NP (重寫 VP) ? John ate NP (重寫 V) ? John ate ART N (重寫 NP) ? John ate the N (重寫 ART) ? John ate the apple (重寫 N) 喬姆斯基的文法層級 0型文法 1型文法 2型文法 3型文法 喬姆斯基 0型文法 ?短語結構文法，無限制
教學課件相關推薦
鄂ICP備17016276號-1