第三章 自動機基礎(1).ppt

產(chǎn)生式形式為 xAy x y 產(chǎn)生式形式為 A aB A a A 產(chǎn)生式形式為 A 形式語言分為四類 由文法產(chǎn)生式的形式不同而區(qū)別 2型語言由2型文法定義 1型語言由1型文法定義 0型語言由0型文法定義 產(chǎn)生式形式為 3型語言由3型文法定義 又稱無限制文法 語言 又稱上下文有關文法 語言 又稱上下文無關文法 語言 又稱正規(guī)文法 語言 注 四類語言為包含關系 且有L0 L1 L2 L3 編譯處理中 主要應用后兩種文法 2 7形式語言的分類問題 A B VN a VT xy VN VT 令 第3章自動機基礎 3 1正規(guī)語言及其描述方法 內(nèi)容提要 自動機 是一種語言模型 是語言的一種識別工具 其中的有限自動機 finiteautomata FA被用來處理正規(guī)語言 后者是編譯程序設計中詞法分析的對象 3 2有限自動機的定義與分類 3 3有限自動機的等價變換1 2 3 4有限狀態(tài)自動機的實現(xiàn)問題 3 5正規(guī)語言描述方法間的相互轉(zhuǎn)換 3 1正規(guī)語言及其描述方法 定義 正規(guī)語言是指由正規(guī)文法定義的語言 程序設計語言中的單詞 大都屬于此種語言 正規(guī)語言有三種等價的表示方法 正規(guī)文法 正規(guī)式 有限自動機 例3 1 G Z A aA A A aA aaA aaaA an n 0 L G an n 0 正規(guī)文法 正規(guī)語言 正規(guī)語言判定示例 例3 2 L1 ambn m 0 n 1 正規(guī)語言 可由正規(guī)文法定義 G1 S S aS bA A bA L1是正規(guī)語言 例3 3 L2 ab n n 1 正規(guī)語言 可由正規(guī)文法定義 G2 S S aA A bB B aA L2是正規(guī)語言 例3 4 L3 anbn n 0 正規(guī)語言 不能由正規(guī)文法定義 正規(guī)文法無法描述a和b數(shù)量上相等 L3不是正規(guī)語言 3 1 1正規(guī)語言的正規(guī)式表示法 正規(guī)式是指由字母表中的符號 通過以下三種運算 也可以使用圓括號 連接起來構(gòu)成的表達式e 連接 或 閉包 設val e L e 分別表示正規(guī)式e的值和語言 則 L e x x val e 即正規(guī)式表示的語言是該正規(guī)式所有值的集合 正規(guī)集 例 ab cde abcde ab cde ab cde a a aa aaa an a a aa aaa an 正規(guī)式表示正規(guī)語言示例 展開 L e3 abnc bn n 0 L e2 ab n n 1 e2 ab e3 ab c b L e1 ambn m 0 n 1 e1 a b b ab bb aaa aab aba abb ab abab ababab abababab ac abc abbc abbbc b bb bbb 例 3 1 2正規(guī)語言的有限自動機表示法 L3 abnc bn n 0 FA1 FA2 FA3 初看起來 有限自動機是帶標記的有向圖 1 2 3 4 狀態(tài)集 其中 開始狀態(tài) 結(jié)束狀態(tài) a b c 字母表 1 a 2 變換 或 有限自動機表示法說明 L3 abnc bn n 0 一個FA 若存在一條從某開始狀態(tài)i到某結(jié)束狀態(tài)j的通路 且這條通路上所有邊的標記連成的符號串為 則 就是一個句子 所有這樣的 的集合 就是該FA表示的語言 圖符說明 運行機制 表示1狀態(tài)遇符號a變到2狀態(tài) e ab c b G S S aA bB A bA c B bB 正規(guī)語言的三種表示法綜合示例 例3 5 L abnc bn n 0 a b c 注 凡是能由上述三種方法表示的語言 一定是正規(guī)語言 反之 凡是不能由上述三種方法表示的語言 一定不是正規(guī)語言 1 正規(guī)文法描述 2 正規(guī)式描述 3 有限自動機描述 FA 表示可接受空串 3 2 1有限自動機的定義 狀態(tài)i遇符號a 變換為狀態(tài)j 3 2有限自動機的定義和分類 變換 二元函數(shù) Q 有限狀態(tài)集 或 定義 有限自動機是一種數(shù)學模型 用于描述正規(guī)語言 可定義為五元組 i a j 其中 i j Q a F 結(jié)束狀態(tài)集 F Q S 開始狀態(tài)集 S Q 字母表 含義 FA Q S F L FA x i FA存在一條從某初始狀態(tài)i到某結(jié)束狀態(tài)j的連續(xù)變換 且每次變換 的邊標記連成的符號串恰好為x 稱x為FA接受 否則拒絕 3 2 2有限自動機怎樣描述語言 令L FA 為自動機FA所描述的正規(guī)語言 則 如右圖有限自動機 即 含義是 j x i S j F 則L FA 的識別過程如下所示 L FA 的生成 或識別 過程示例 第一條通路 FA1 第二條通路 FA2 L FA abnc bn n 0 因而 接受空串的FA的典型特征 3 2 3有限自動機的兩種表現(xiàn)形式 例3 6 有限自動機 FA Q S F 其中 Q 1 2 3 4 a b c S 1 2 F 3 4 FA的兩種表現(xiàn)形式 狀態(tài)圖 變換表 變換表結(jié)構(gòu) 行 狀態(tài) 列 符號 表項 變換后狀態(tài) 開始狀態(tài)結(jié)束狀態(tài) 例3 7 A abnc ab n n 0 或 變換函數(shù)不單值 如 一 開始狀態(tài)不唯一 不好用 1 a 2 4 也不好用 方法一 聯(lián)合式 方法二 組合式1 比較 二 帶有 邊 還是不好用 FA的構(gòu)造 有限自動機的構(gòu)造示例1 或 有限自動機的構(gòu)造示例2 方法三 確定式 a b b b c b a a c c DFA 確定的有限自動機 DFA 特征 開始狀態(tài)唯一 變換函數(shù)單值 不帶 邊 非確定的有限自動機 NFA 帶有 邊的非確定的有限自動機 NFA 不帶有 邊的非確定的有限自動機 NFA 不能全部具備上述特征者 3 2 4有限自動機的分類 有限自動機的分類示例 FA1 例3 8 試分別指出下述有限自動機的分類情況 FA2 FA3 FA5 結(jié)論 DFA FA2 NFA FA4 FA5 FA1 FA3 NFA FA4 習題 習題3 1 解釋下列詞語 正規(guī)文法 正規(guī)語言 有限自動機 確定的有限自動機 非確定的有限自動機 習題3 2 給定正規(guī)語言 構(gòu)造有限自動機 無符號整數(shù) 正規(guī)式為e dd 標識符集 正規(guī)式為e d A an ban n 0 第2章習題解答 習題2 5 P27 2 5 證明下面文法是二義性文法S iSeS iS i 證 因為句型iiSeS有下述兩棵不同的語法樹 和 所以所屬文法是二義性文法 習題2 6 G S S aAcBe A Ab b B d 證明 aAbcde是一個句型 畫出句型 的語法樹 指出句型 的短語 簡單短語和句柄 第2章習題解答 習題2 12 消除下述文法的直接左遞歸 G S E E T E T T 解 消除直接左遞歸公式 整理 E E T E T T 有 G S E T T A A A A A A A 或 G S E TE E TE 令 E E T T 第2章習題解答5 習題2 11 化簡下述文法 G S S aSab bAB A bB a B aA bC abB baA D Cbc abc 解 刪除無用產(chǎn)生式 自定己 不終結(jié) 不可達 找自定己產(chǎn)生式 如A A 無自定己者 構(gòu)造可終結(jié)非終結(jié)符集Vvt 構(gòu)造可達非終結(jié)符集VAR G S S aSab bAB A bB a B aA b 刪除不可達非終結(jié)符 C D后得 無不終結(jié)者 A B C D S S A B 謝謝收看 再見 正規(guī)式描述語言的簡單運算例 L a a L a b L a L b a b L a b L a L b a