形式言語とオートマトン
担当教員
授業の到達目標及びテーマ
・オートマトンとは何か理解する ・有限オートマトンと正規言語の関係を理解する ・文脈自由言語についてその特徴・性質を理解する ・プッシュダウンオートマトンとは何かを理解する ・チューリングマシンについて理解する
授業の概要と方法
この講義は情報科学の様々な側面の基礎をなすオートマトンと形式言語について学ぶ。オートマトンはハードウェアからソフトウェアに至るまでの情報科学の全ての側面において、動作のモデルを定義・表現・設計するたために使われる非常に重要な概念である。講義の前半では、このオートマトンの理解を目標において講義を進める。講義の後半では、そのオートマトンの入力として与えられる形式言語について学ぶ。形式言語の知識ははプログラミング処理系の理解のためには必須である。 なお、毎回の講義は、1時間説明を行なったあと、30分を小テストに当てる。
授業計画
| 回 | テーマ | 内容 |
|---|---|---|
| 1 | 序論 | 1.オートマトンとは計算機のモデル 2.形式言語は言語のモデル 3.オートマトンと形式言語の関係 4.チョムスキー階層 5.オートマトンの応用 |
| 2 | 有限オートマトン(1) | 1.オートマトンの状態遷移図表現 2.集合 3.五字組表現 |
| 3 | 有限オートマトン(2) | 1.有限ートマトンの例 2.様相、受理・拒否 |
| 4 | 有限オートマトン(3) | 1.有限オートマトン演習 |
| 5 | 非決定性有限オートマトン(1) | 1.決定性オートマトンと非決定性オートマトン 2.非決定性オートマトンの状態遷移図 3.非決定性オートマトンの五字組表現 |
| 6 | 非決定性有限オートマトン(2) | 1.空動作を伴うオートマトン 2.空動作を伴うオートマトンの状態遷移図 3.空動作を伴うオートマトンの五字組表現 4.決定性オートマトンと非決定性オートマトンの同等性 |
| 7 | プッシュダウンオートマトン | 1.決定的プッシュダウンオートマトン 2.決定的プッシュダウンオートマトンの七字組表現 3.決定的プッシュダウンオートマトンの動作 4.決定的プッシュダウンオートマトンの状態遷移図 5.非決定的プッシュダウンオートマトン 6.非決定的プッシュダウンオートマトンの七字組表現 7.非決定的プッシュダウンオートマトンの動作 8.非決定的プッシュダウンオートマトンの状態遷移図 |
| 8 | 中間試験 | 主にオートマトンの部分について試験を行う |
| 9 | 文法(1) | 1.正規文法 2.言語の生成装置としての形式文法 3.オートマトンと文法の対比・階層性 4.文脈自由文法 |
| 10 | 文法(2) | 1.文法の種類 2.文脈自由文法の例 |
| 11 | 文法(3) | 1.文法演習 |
| 12 | 文脈依存文法(1) | 1.文脈自由文法の例 |
| 13 | 文脈依存文法(2) | 1.文脈自由文法と木構造 2.2分木からチョムスキー標準系に |
| 14 | オートマトンと形式言語の関係 | 正規文法と有限オートマトンの関係 1.正規表現による正規言語の表現 2.有限オートマトンで表現できない文脈自由文法 3.閉包性 4.チョムスキー標準系 5.グライバッハ標準系 |
| 15 | まとめ | 1 - 14回の講義のまとめを行う |
授業外に行うべき学習活動
教科書の内容をよく読んでおくこと。講義では、正しく理解しているかどうか確認を行うようにする
テキスト
米田、広瀬、大里、大川著「オートマトン・言語理論の基礎」近代科学社
参考書
J.ホップクロフト他著「オートマトン 言語理論 計算論I」サイエンス社 富田、横森著「オートマトン・言語理論」森北出版
成績評価基準
以下の配分で評価する 中間試験 40% 期末試験 60% なお、評価は 出席 80%以上(欠席は3回まで) を対象とする。 これに満たないものは評価の対象とはならない。
前年度の授業改善アンケートからの気づき
特になし