第11章圖象模式識別-文庫吧資料
2024-10-06 16:42本頁面
【正文】 元，一組確定這些基元相互作用的規(guī)則和一個識別器（稱為自動機） 字符串結構識別 樹結構識別 學習和推理 第 30頁 第 10講 章毓晉 (THEEIE) 字符串結構識別 1. 字符串文法 文法（語法）：一組句法規(guī)則，控制字符集中符 號產生句子的過程 語言：由一個文法 G所產生的一組句子，記為 L(G) 句子：符號的串，代表模式，語言對應模式類 ? 文法 G1中的句法規(guī)則只允許產生對應類 s1中模式的句子，文法 G2中的句法規(guī)則只允許產生對應類 s2中模式的句子 識別：對一個表示未知模式的句子，決定在哪個 語言中模式表示了一個可成立的句子 第 31頁 第 10講 章毓晉 (THEEIE) 字符串結構識別 1. 字符串文法 定義一個四元組： ? N為一個有限的變量集，稱為非終結符號集 用大寫字母 A, B, …, S, … 代表非終結符號 ? T為一個有限的常量集，稱為終結符號集 用小寫字母 a, b, c, … 表示終結符號 ? P是一組稱為產生式的重寫規(guī)則集 ? S在 N中，稱為起始符號 ) , , ,( SPTNG ?第 32頁 第 10講 章毓晉 (THEEIE) 字符串結構識別 1. 字符串文法 字符串文法的特點由產生式規(guī)則的形式決定： ? 規(guī)則文法 產生式規(guī)則： A ? aB或 A ? a ? 前后文無關文法 它只包含形式為 A ? a的產生式規(guī)則， a 在集(N ? T) * – ? 中 a 可以是除了空集以外的由終結符號和非終結符號組成的任何字符串 第 33頁 第 10講 章毓晉 (THEEIE) 字符串結構識別 1. 字符串文法 文法 G = (N, T, P, S) N = {A, B, C}， T = {a, b, c} P = {S ? aA, A ? bA, A ? bB, B ? c} S ? aA ? abA ? abbA ? abbbA ? abbbbA ? abbbbbB ? abbbbbc 語言： L(G) = {abnc | n ≥ 1}， bn代表 b的 n次重復 ( a ) ( b ) ( c )第 34頁 第 10講 章毓晉 (THEEIE) 字符串結構識別 2. 語義應用 句法確定了目標的結構，而語義主要與其正確性有關 通過使用語義信息，可用較少的句法規(guī)則以描述較廣泛（但是有限）的模式類 第 35頁 第 10講 章毓晉 (THEEIE) 字符串結構識別 3. 用自動機作為字符串識別器 自動機能識別一個輸入模式字符串是否屬于與自動機關聯的語言 有限自動機：由規(guī)則語法產生的語言識別器 Q是一個有限的非空狀態(tài)集； T 是一個有限的輸入字符集； ? 是一個從 Q ? T（即由 Q和 T的元素組成的排序對集合）到所有 Q子集的映射； q0是初始狀態(tài)； F（ Q的一個子集）是一個最終或可接收狀態(tài)的集合 ), , ,( 0 FqTQA f ??第 36頁 第 10講 章毓晉 (THEEIE) 字符串結構識別 3. 用自動機作為字符串識別器 有限自動機狀態(tài)圖 Q = {q0, q1, q2} T = {a, b} F = {q0} 映射規(guī)則： ? (q0, a) = {q2}， ? (q0, b) = {q1}， ? (q1, a) = {q2}， ? (q1, b) = {q0}， ? (q2, a) = {q0}， ? (q2, b) = {q1} 能識別字符串 abbabb，但不能識別字符串 aabab 第 37頁 第 10講 章毓晉 (THEEIE)
教學課件相關推薦
鄂ICP備17016276號-1