第三章 自動(dòng)機(jī)基礎(chǔ)(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ān)文法 語言 又稱上下文無關(guān)文法 語言 又稱正規(guī)文法 語言 注 四類語言為包含關(guān)系 且有L0 L1 L2 L3 編譯處理中 主要應(yīng)用后兩種文法 2 7形式語言的分類問題 A B VN a VT xy VN VT 令 第3章自動(dòng)機(jī)基礎(chǔ) 3 1正規(guī)語言及其描述方法 內(nèi)容提要 自動(dòng)機(jī) 是一種語言模型 是語言的一種識(shí)別工具 其中的有限自動(dòng)機(jī) finiteautomata FA被用來處理正規(guī)語言 后者是編譯程序設(shè)計(jì)中詞法分析的對(duì)象 3 2有限自動(dòng)機(jī)的定義與分類 3 3有限自動(dòng)機(jī)的等價(jià)變換1 2 3 4有限狀態(tài)自動(dòng)機(jī)的實(shí)現(xiàn)問題 3 5正規(guī)語言描述方法間的相互轉(zhuǎn)換 3 1正規(guī)語言及其描述方法 定義 正規(guī)語言是指由正規(guī)文法定義的語言 程序設(shè)計(jì)語言中的單詞 大都屬于此種語言 正規(guī)語言有三種等價(jià)的表示方法 正規(guī)文法 正規(guī)式 有限自動(dòng)機(jī) 例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ī)式是指由字母表中的符號(hào) 通過以下三種運(yùn)算 也可以使用圓括號(hào) 連接起來構(gòu)成的表達(dá)式e 連接 或 閉包 設(shè)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ī)語言的有限自動(dòng)機(jī)表示法 L3 abnc bn n 0 FA1 FA2 FA3 初看起來 有限自動(dòng)機(jī)是帶標(biāo)記的有向圖 1 2 3 4 狀態(tài)集 其中 開始狀態(tài) 結(jié)束狀態(tài) a b c 字母表 1 a 2 變換 或 有限自動(dòng)機(jī)表示法說明 L3 abnc bn n 0 一個(gè)FA 若存在一條從某開始狀態(tài)i到某結(jié)束狀態(tài)j的通路 且這條通路上所有邊的標(biāo)記連成的符號(hào)串為 則 就是一個(gè)句子 所有這樣的 的集合 就是該FA表示的語言 圖符說明 運(yùn)行機(jī)制 表示1狀態(tài)遇符號(hào)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 有限自動(dòng)機(jī)描述 FA 表示可接受空串 3 2 1有限自動(dòng)機(jī)的定義 狀態(tài)i遇符號(hào)a 變換為狀態(tài)j 3 2有限自動(dòng)機(jī)的定義和分類 變換 二元函數(shù) Q 有限狀態(tài)集 或 定義 有限自動(dòng)機(jī)是一種數(shù)學(xué)模型 用于描述正規(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ù)變換 且每次變換 的邊標(biāo)記連成的符號(hào)串恰好為x 稱x為FA接受 否則拒絕 3 2 2有限自動(dòng)機(jī)怎樣描述語言 令L FA 為自動(dòng)機(jī)FA所描述的正規(guī)語言 則 如右圖有限自動(dòng)機(jī) 即 含義是 j x i S j F 則L FA 的識(shí)別過程如下所示 L FA 的生成 或識(shí)別 過程示例 第一條通路 FA1 第二條通路 FA2 L FA abnc bn n 0 因而 接受空串的FA的典型特征 3 2 3有限自動(dòng)機(jī)的兩種表現(xiàn)形式 例3 6 有限自動(dòng)機(jī) 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) 列 符號(hào) 表項(xiàng) 變換后狀態(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)造 有限自動(dòng)機(jī)的構(gòu)造示例1 或 有限自動(dòng)機(jī)的構(gòu)造示例2 方法三 確定式 a b b b c b a a c c DFA 確定的有限自動(dòng)機(jī) DFA 特征 開始狀態(tài)唯一 變換函數(shù)單值 不帶 邊 非確定的有限自動(dòng)機(jī) NFA 帶有 邊的非確定的有限自動(dòng)機(jī) NFA 不帶有 邊的非確定的有限自動(dòng)機(jī) NFA 不能全部具備上述特征者 3 2 4有限自動(dòng)機(jī)的分類 有限自動(dòng)機(jī)的分類示例 FA1 例3 8 試分別指出下述有限自動(dòng)機(jī)的分類情況 FA2 FA3 FA5 結(jié)論 DFA FA2 NFA FA4 FA5 FA1 FA3 NFA FA4 習(xí)題 習(xí)題3 1 解釋下列詞語 正規(guī)文法 正規(guī)語言 有限自動(dòng)機(jī) 確定的有限自動(dòng)機(jī) 非確定的有限自動(dòng)機(jī) 習(xí)題3 2 給定正規(guī)語言 構(gòu)造有限自動(dòng)機(jī) 無符號(hào)整數(shù) 正規(guī)式為e dd 標(biāo)識(shí)符集 正規(guī)式為e d A an ban n 0 第2章習(xí)題解答 習(xí)題2 5 P27 2 5 證明下面文法是二義性文法S iSeS iS i 證 因?yàn)榫湫蚷iSeS有下述兩棵不同的語法樹 和 所以所屬文法是二義性文法 習(xí)題2 6 G S S aAcBe A Ab b B d 證明 aAbcde是一個(gè)句型 畫出句型 的語法樹 指出句型 的短語 簡(jiǎn)單短語和句柄 第2章習(xí)題解答 習(xí)題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章習(xí)題解答5 習(xí)題2 11 化簡(jiǎn)下述文法 G S S aSab bAB A bB a B aA bC abB baA D Cbc abc 解 刪除無用產(chǎn)生式 自定己 不終結(jié) 不可達(dá) 找自定己產(chǎn)生式 如A A 無自定己者 構(gòu)造可終結(jié)非終結(jié)符集Vvt 構(gòu)造可達(dá)非終結(jié)符集VAR G S S aSab bAB A bB a B aA b 刪除不可達(dá)非終結(jié)符 C D后得 無不終結(jié)者 A B C D S S A B 謝謝收看 再見 正規(guī)式描述語言的簡(jiǎn)單運(yùn)算例 L a a L a b L a L b a b L a b L a L b a