形式言語 と オートマトン 第13回 鳥取大学工学研究科 情報エレクトロニクス専攻 田中美栄子 本日の予定 今日全ての例題は答えを出しません,ノートを取って考えてください. 形式言語とオートマトン 試験の考察点(80%) 1.言語の階層構造:言語とオートマトンの対応関係など 2.有限状態オートマトン 正規表現 3.文脈自由文法のCHOMSKY標準形及び言語導出(2分木) 4.NFAをDFAに書き換えること: アルゴリズム2.1/2.2 5.状態遷移図 形式言語とオートマトン 5字組及び状態遷移表の書き方 試験の考察点 1.言語の階層構造:言語とオートマトンの対応関係など 形式言語とオートマトン 1.言語の階層構造:言語とオートマトンの対応関係など オートマトン(左)と文法(右)の対応する階層性 FSA 正規文法 PDA 文脈自由文法 LBA 文脈依存文法 TM 句構造文法 形式言語とオートマトン 閉 包 性 • 全てのクラスi-0,1,2,3に属する言語は、和、連結、* に対して 。 • 文脈自由言語は補集合や交わりの • 交わりはドモルガンにより補集合と和で書けるから、 。 。 • 正規言語は 。 • Type0は 。 • Type1は補集合の元で閉じることが1988判明した。 (Neil Immerman、SIAM J.Computing vol.17-5) 形式言語とオートマトン 閉 包 1. 性 は、 、 、 、などにおいて 2. は に於いて よって に於いても 反例は 、 において二つの積集合は であるが、 形式言語とオートマトン 、 、 、 1.言語の階層構造:言語とオートマトンの対応関係など 例 L {a b | 1 ≦ m ≦ n ≦ 2m} m n は (1) (3) 言語に属し, (2) 文法で生成でき, オートマトンで識別できる. 形式言語とオートマトン 試験の考察点 2.有限状態オートマトン 形式言語とオートマトン 正規表現 2.有限状態オートマトン 正規表現 正規表現に書き換えると? L = {a3n | n>=0} = {aaa}* L = (a3)* L = {an | n>=0} = {a}* L = a* L={ab,ba} ={ab} U {ba} L=ab+ba L={aa}{a,b}*{bbb} 形式言語とオートマトン L=a2(a+b)*b3 2.有限状態オートマトン 正規表現 a 有限状態オートマトン 正規表現 a+b 正規表現は 有限状態オートマトン a,b 形式言語とオートマトン a* 正規表現 2.有限状態オートマトン 例: a b ε c c D 図示のNFAが受理する言語の正規表現を求めてください 形式言語とオートマトン 試験の考察点 3.文脈自由文法のCHOMSKY標準形及び言語導出(2分木) 形式言語とオートマトン どんな文脈自由言語(ただし,εを含まないも の)も,次の形式の規則のみを使って表せる ことを示したい A → BC または A → a、 ただし、A、B、Cは非 終端記号、 aは終端記号である(必要に応じて 変数を増やす) 形式言語とオートマトン G N, , P, S0 N {S} {a, b} P {S aSb,S ab} S0 S S aSb S ASB, A a, B b, C SB, S AC S ab S AB 規則を:A → BCまたはA → aに変更する 形式言語とオートマトン Chomsky標準形なら2分木になる P {S AB, A a, B b, S AC, C SB} S aabbの導出木は: A C B S A B a 形式言語とオートマトン a b b 3.文脈自由文法のCHOMSKY標準形及び言語導出(2分木) 例: 文法G=(V,T,P,S), V={A}, T={a,b}, P={A→aAb, A→AA, A→ab}, S={A}によって、abaabb という語が導出される過程はどのようになるか、 空白を埋めよ A ⇒ (1) ⇒ (2) ⇒(3) ⇒ abaabb これと同じ言語を生成する別の文法を同等な文法と呼ぶ。上のGと同等で文 法G’をChomsky標準形といい、G’=(V’,T,P’,S)を構成し、abaabbの導出木を作れ 形式言語とオートマトン 試験の考察点 4.NFAをDFAに書き換えること: アルゴリズム2.1/2.2 形式言語とオートマトン 4.NFAをDFAに書き換えること: アルゴリズム2.1/2.2 例: a b ε c c D 図示のNFAと同等なDFAの状態遷移図を描け. 形式言語とオートマトン 試験の考察点 5.状態遷移図 形式言語とオートマトン 5字組及び状態遷移表の書き方 有限オートマトンの5字組み表現 5字組み表現 M= <Q,Σ,δ,q0,F> 形式言語とオートマトン 5.状態遷移図 5字組及び状態遷移表の書き方 例1: a b ε c c D 図示のNFAと同等なDFAを5字組で表せ.また、NFAとDFAの状 態遷移表を描け. 形式言語とオートマトン 5.状態遷移図 5字組及び状態遷移表の書き方 例2: 正規表現b*a(a+b)*bbについてNFAとそれに同等な DFAの状態遷移表と状態遷移図を作れ. 正規表現分からないと だめですよ. 形式言語とオートマトン 以上です。 講義pptと小テストの答えはホームページで確認してください: http://irene.ike.tottori-u.ac.jp/mieko/2014autom.html 形式言語とオートマトン
© Copyright 2024 ExpyDoc