形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ 形式言語とオートマトン 第14回　プッシュダウンオートマトンと全体のまとめ 2017年 1月10日 中島

プッシュダウンオートマトン(PDA) チョムスキーの言語の分類 3 階層 文法 受理するオートマトン 正規言語（正規表現） 有限オートマトン 2 文脈自由言語 プッシュダウンオートマトン 1 文脈依存言語 線形拘束オートマトン 句構造言語（自由言語） チューリングマシン

プッシュダウンオートマトン(PDA) PDA ＝ 有限オートマトン + プッシュダウンスタック 有限オートマトン 有限状態制御部 入力テープ a b a b b プッシュダウンスタック (スタックメモリ) 読み取りヘッド 読み書きヘッド （スタックポインタ） 有限状態制御部 A B Z PDA は文脈自由文法と同じ言語クラスを表現する

記憶装置としてのスタック 「後入れ先出し （LIFO: Last In First Out)」の記憶装置 ２つの操作 スタックメモリ ２つの操作 スタック ポインタ （SP） push (X)：　　Xをスタックに記憶する Y = pop()：　スタックから値を取り出しYに入れる 20 10 Z 初期プッシュダウン記号 動作： 後に入れたものが先に出てくる Z

記憶装置としてのスタック 「後入れ先出し （LIFO: Last In First Out)」の記憶装置 ２つの操作 スタックメモリ ２つの操作 スタック ポインタ （SP） push (X)：　　Xをスタックに記憶する Y = pop()：　スタックから値を取り出しYに入れる 20 10 Z 初期プッシュダウン記号 動作： 後に入れたものが先に出てくる push(10) 10 Z

記憶装置としてのスタック 「後入れ先出し （LIFO: Last In First Out)」の記憶装置 ２つの操作 スタックメモリ ２つの操作 スタック ポインタ （SP） push (X)：　　Xをスタックに記憶する Y = pop()：　スタックから値を取り出しYに入れる 20 10 Z 初期プッシュダウン記号 動作： 後に入れたものが先に出てくる 20 push(10), push(20) 10 Z

記憶装置としてのスタック 「後入れ先出し （LIFO: Last In First Out)」の記憶装置 ２つの操作 スタックメモリ ２つの操作 スタック ポインタ （SP） push (X)：　　Xをスタックに記憶する Y = pop()：　スタックから値を取り出しYに入れる 20 10 Z 初期プッシュダウン記号 動作： 後に入れたものが先に出てくる push(10), push(20), Y1=pop() 10 Z Y1=20

記憶装置としてのスタック 「後入れ先出し （LIFO: Last In First Out)」の記憶装置 ２つの操作 スタックメモリ ２つの操作 スタック ポインタ （SP） push (X)：　　Xをスタックに記憶する Y = pop()：　スタックから値を取り出しYに入れる 20 10 Z 初期プッシュダウン記号 動作： 後に入れたものが先に出てくる push(10), push(20), Y1=pop(), Y2=pop() Z Y1=20 Y2=10

プッシュダウンオートマトン(PDA)の定義 PDA M = (Q, Σ, Γ, δ, S, Z) Q: 内部状態の集合 Σ： 入力テープ記号の集合（入力アルファベット） Γ： プッシュダウン記号の集合 δ： 状態遷移関数 δ： Q×(Σ ＋ {ε}) × Γ → Ρ(Q×Γ*) S： 初期状態 S∈Q Z： 初期プッシュダウン記号 Z∈Γ

PDAの例： { anbn | n ≧ 1なる整数 } ・・・ 文脈自由文法： S → aSb | ab A3 B3 A2 B2 A1 B1 文脈自由文法：　 構文図式が簡略化できない S S → aSb | ab a b S 文　ω = aaabbb に対する導出木 有限オートマトンでは表現できない ・・・ S a b ε A3 B3 S a b ε A2 B2 S a b ε a a a b b b A1 B1

（Zをpushで戻し続けてAをpush) PDAの例：　{ anbn | n ≧ 1なる整数 } 状態遷移グラフ (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε 状態：　q0へ遷移 スタック：　Z→AZ （Zをpushで戻し続けてAをpush) {(q0, AA), (q1, A)} {(q1, ε)} δ a b (q0, Z) (q0, A) (q1, Z) (q1, A) {(q0, AZ), (q1, Z)} ø 遷移関数 状態：　q1へ遷移 スタック：　A→A （Aをpushで戻し現状維持) 状態：　q1へ遷移 スタック：　A→ε （何もしない結局１つ減る) 状態 スタック読取り結果（１回pop)

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b Z (b, Z) / ε 1-1 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A Z (b, Z) / ε 1-2 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A Z (b, Z) / ε 2-1 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A A Z (b, Z) / ε 2-2 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 A A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A A Z (b, Z) / ε 3-1 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 A A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A A A Z 3-2 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b A 有限状態制御部 A A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A A A Z 4-1 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b A 有限状態制御部 A A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A A Z (b, Z) / ε 4-2 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 A A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A A Z (b, Z) / ε 5-1 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 A A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A Z (b, Z) / ε 5-2 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b A Z (b, Z) / ε 6-1 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 A Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b Z (b, Z) / ε 6-2 (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 Z

PDAの例： { anbn | n ≧ 1なる整数 } 有限状態制御部 q0 q1 a a a b b b Z (b, Z) / ε 7-E (a, Z) / ZA (b, Z) / ε (a, Z) / Z, (a, A) / A q0 q1 (a, A) / AA (b, A) / ε a a a b b b 有限状態制御部 Z

PDAの最後に： 木構造とスタック 数式の記法（構文木）←FA／正規表現でカバーできない 木構造をたどる処理（再帰的な処理） 文脈自由文法　（再帰的な言語の表現） 木構造をたどる処理（再帰的な処理） 　→　スタックを使って処理できる 例：　逆ポーランド記法の電卓　（スタックによる計算）

授業のまとめ

正規言語＜文脈自由言語＜文脈依存言語＜句構造言語 形式言語 と　オートマトン チョムスキーの言語の分類 制限大 階層 文法 受理するオートマトン 3 正規言語（正規表現） 有限オートマトン 2 文脈自由言語 プッシュダウンオートマトン 1 文脈依存言語 線形拘束オートマトン 句構造言語（自由言語） チューリングマシン 小 正規言語＜文脈自由言語＜文脈依存言語＜句構造言語 正規表現と有限オートマトンは等価である ほとんどのプログラミング言語は文脈自由文法で定義 文脈依存文法は、自然言語のモデルとして十分強力

正規表現と有限オートマトン NFA DFA ε-NFA 正規表現 FAと正規表現は同じ言語クラスを表現するという意味で同等 サブセット構成法 ε動作の除去 DFA 最小化 ε-NFA 正規表現 帰納的構成法 線形再帰方程式 授業：「変換アルゴリズムを示すことで同等である」ことを証明

有限オートマトンの応用例: 正規表現による言語処理 要求分析・設計における仕様記述／検証 コンパイラ（文脈自由文法）へつながる 認識技術 自然言語理解 文字認識 セルオートマトン 計算可能性理論 複雑適応系、数理生物学 微小構造モデリング

応用例： システムの仕様記述 FAを使って，システムの機能仕様（入力→出力）を記述する 例） 電灯のオンオフ ２つの表現方法 ミーリー機械： 応用例： システムの仕様記述　 FAを使って，システムの機能仕様（入力→出力）を記述する 例）　電灯のオンオフ PW ２つの表現方法 PW/ON ミーリー機械： 　出力が，入力と現在の 　状態から決まる 消灯中 点灯中 PW/OFF ムーア機械： 出力が，遷移先の状態 　で決まる PW 消灯中/OFF 点灯中/ON PW

応用例： 機械（システム）の仕様記述 例） ストップウォッチ 仕様記述 LB RB LB： 計測開始/停止 例）　ストップウォッチ LB RB LB：　計測開始/停止 RB：　クリア（停止時）/ラップ（計測時） 仕様記述 RB/LAP追加表示 初期画面 LB 計測中／開始 LB LB 利点 抜けなく正確に記述できる レビューがしやすい RB/クリア 停止中 ／停止

■ほぼ機械的にコーディングすることができる！！ 状態遷移図からコーディングへ イベント駆動型：　イベントに対する動作を状態別に記述 状態駆動型：　　　状態に対する動作をイベント別に記述 ■ほぼ機械的にコーディングすることができる！！

簡潔でしょう？ イベント駆動型による 実装例 戻る enum KT_State {初期画面, 計測中, 停止中}; enum KT_Event {LB, RB, 単位時間経過}; int main(void) { int T = 0; /* 表示時間 */ enum KT_State state = 初期画面; while (TRUE) { enum KT_Event event = get_event(); if (event == LB) { if (state == 初期画面 || state == 停止中) state = 計測中; else if (state == 計測中) state = 停止中; } else if (event == RB) { if (state == 計測中) { display_lap(); else if (state == 停止中) { state = 初期画面; T = 0; display_clear(); if (event = 単位時間経過) { if (state == 計測中) { T += unitTime; display_time(T); return 0; イベント駆動型による 実装例 簡潔でしょう？ 戻る

授業の実施内容 (1/2) 1. 概要 9/20 2. 形式言語と帰納的表現 9/27 3. 順序機械： 10/4 授業の実施内容　(1/2) 1. 概要 9/20 　　・オートマトンと言語、チョムスキの４階層 2. 形式言語と帰納的表現 9/27 　　・語、言語、クリーネ閉包、スター演算 教科書： pp. pp.32-39 3. 順序機械： 10/4 　　・ミーリ機械、ムーア機械 教科書: pp.83-88 4. 有限オートマトン（１） 10/11 　　・決定性オートマトン（DFA），言語の受理 教科書: pp.89-95 5. 正規言語 10/18 　　・正規表現、線形再帰方程式（DFAからの変換） 教科書: pp.96-104 6. 有限オートマトン（2） 10/25 　　・非決定性オートマトン（NFA）、DFA化 教科書:pp.105-109 7. 有限オートマトン（3） 11/8 　　・εNFA、NFA化、 DFAへの変換 教科書:pp.109-115 8. 中間テスト、講評 11/15

授業の実施内容 (2/2) 9. 有限オートマトン（３） 11/22 10. 有限オートマトン（４） 11/29 授業の実施内容　(2/2) 9. 有限オートマトン（３） 11/22 　　・ Myhill-Nerodeの定理、同値類 教科書:pp.115-119 10. 有限オートマトン（４） 11/29 　　・ 最小化，応用 教科書:pp.115-125 11. 有限オートマトン（５） 12/6 　　・ 中置、ポーランド、逆ポーランド記法 教科書:pp.41-43,78-80 12. 形式言語とＢＮＦ記法： 12/13 　　・　メタ言語、構文図式 教科書:pp.43-47 13. 形式言語理論と文脈自由文法 12/20 　　・　形式文法，文脈自由文法，導出木 教科書:pp. 145-153 14. PDAとまとめ 1/10 　　 教科書:pp. 125-131 15. テストと解説 1/17 教科書:pp.30-123

期末試験 教科書のみ持ち込みあり 範囲 数式の文法間変換 構文図式＋導出木 順序機械 正規表現による言語処理 正規表現と有限オートマトンの間の変換 （P28のアルゴリズム）

文脈自由文法 戻る Basic Visual Basic FORTRAN77 FORTRAN90/95 COBOL65 COBOL言語 （初心者用言語） Visual Basic FORTRAN77 FORTRAN90/95 COBOL65 COBOL言語 (事務処理用言語) COBOL2002 FORTRAN言語 (科学計算用言語) アセンブラ言語 Algol （BNF） BCPL C ANSI C C++ Simula Smalltalk Smalltalk80 Objective-C Java C# Ruby Lisp （関数型言語） Prolog （論理型言語） Lisp1.5 Common Lisp Perl PHP JavaScript awk Python 文脈自由文法 スクリプト型言語 戻る