2024年度 学院等開講科目 情報理工学院 情報工学系
オートマトンと形式言語
- 開講元
- 情報工学系
- 担当教員
- 篠田 浩一
- 授業形態
- 講義 (対面型)
- メディア利用科目
- -
- 曜日・時限
(講義室) - 火5-6 (WL2-301(W631)) / 金5-6 (WL2-301(W631))
- クラス
- -
- 科目コード
- CSC.T251
- 単位数
- 200
- 開講時期
- 2024年度
- 開講クォーター
- 2Q
- シラバス更新日
- 2025年3月17日
- 使用言語
- 日本語
シラバス
授業の目的（ねらい）、概要
本講義では，プログラム言語処理・自然言語処理の基礎について論じ，句構造文法，正規表現，有限オートマトン，プッシュダウンオートマトン，形式言語の性質について講義する．
形式言語について生成する手段と認識する機械の二つの観点から学ぶことにより，言語処理に関連する基礎理論を理解することをねらいとしている．
到達目標
本講義を履修することにより，以下の知識と能力を修得する．
1) 正規言語と文脈自由言語の定義と性質を理解する．
2) 正規文法と文脈自由文法について定義を理解し，標準形への変換等に関する問題を解くことができる．
3) 決定性／非決定性有限オートマトンの定義を理解し，文法に対応するオートマトンを生成する問題などを解くことができる．
4) プッシュダウンオートマトンの定義を理解し，関連するアルゴリズムに関する問題を解くことができる．
キーワード
句構造文法，正規言語，文脈自由言語，正規文法，文脈自由文法，正規表現，有限オートマトン，プッシュダウン・オートマトン，反復補題
学生が身につける力
- 専門力
- 教養力
- コミュニケーション力
- 展開力 (探究力又は設定力)
- 展開力 (実践力又は解決力)
授業の進め方
1) 講義のはじめに前回講義の復習と演習問題の解説を行う．
2) 講義の後半(30分程度)で講義内容に演習問題を出題する．
授業計画・課題
| 授業計画 | 課題 | |
|---|---|---|
| 第1回 | イントロダクション，句構造文法 | 形式言語，句構造文法，列の導出 |
| 第2回 | 正規文法 | 正規文法，正規言語，正規言語の和集合・連接・クリーネ閉包，ε生成規則の除去 |
| 第3回 | 有限オートマトン | オートマトンの形式的定義，状態遷移図，決定性有限オートマトン(DFA)，非決定性有限オートマトン(NFA) |
| 第4回 | 正規文法と有限オートマトン | NFAからDFAへの変換，NFAに対応する正規文法の導出 |
| 第5回 | ε遷移を含むオートマトン | ε遷移を含むオートマトン，ε遷移の除去，和集合・補集合・共通集合・連接・クリーネ閉包に対するNFA |
| 第6回 | 決定性有限オートマトンの最小化 | DFAの状態数最小化アルゴリズム，最小性の証明．一意性の証明 |
| 第7回 | 正規言語の反復補題 | 正規言語の反復補題，正規言語ではないことの証明法 |
| 第8回 | 正規表現からオートマトンへの変換，オートマトンから正規表現への変換 | ボトムアップ法，トップダウン法，Kleeneの方法，再帰方程式を解く方法 |
| 第9回 | 正規言語・有限オートマトンに関する復習，中間試験 | 正規言語・有限オートマトンに関する復習と中間試験 |
| 第10回 | 文脈自由文法(CFG) | 文脈自由文法，文脈自由言語，導出木，曖昧性，ε生成規則の除去 |
| 第11回 | チョムスキーの標準形 | チョムスキーの標準形(CNF)，単位生成規則の除去 |
| 第12回 | 文脈自由言語(CFL)の反復補題，Ogdenの補題 | CNFに対する導出木，文脈自由言語の反復補題，Ogdenの補題，文脈自由言語ではないことの証明法(反復補題，Ogdenの補題による) |
| 第13回 | 非決定性プッシュダウンオートマトン(NPDA)，決定性プッシュダウンオートマトン(DPDA) | 非決定性プッシュダウンオートマトン（形式的定義，状態遷移図，受理する言語），時点表示，決定性プッシュダウンオートマトン，決定性文脈自由言語(DCFL) |
| 第14回 | 文脈自由文法とプッシュダウンオートマトンの等価性 | 文脈自由文法に対応するNPDAの構成法，空スタックで受理する言語，NPDAに対応する文脈自由文法の生成法 |
準備学修(事前学修・復習)等についての指示
学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。
教科書
R. Smith 著，吉田 敬一 他訳 『コンピュータサイエンスのための言語理論入門』 共立出版，ISBN: 978-4320022799
参考書、講義資料等
J. Hopcroft, R. Motowani, J. Ullman 著，野崎 昭弘， 高橋 正子，町田 元，山崎 秀記 訳 『オートマトン，言語理論，計算論Ｉ, 第2版』 サイエンス社，ISBN: 978-4781910260
成績評価の方法及び基準
講義で扱う形式言語の性質，句構造文法，オートマトン，等に関する理解とその応用力を評価する．
配点は各回の演習問題40%，中間試験30%，期末試験30%とする．
関連する科目
- GRE.C101 ： 情報基礎学第一
- GRE.C102 ： 情報基礎学第二
- CSC.T241 ： 計算基礎論
- CSC.T372 ： コンパイラ構成
- ART.T459 ： 自然言語処理
履修の条件・注意事項
履修の条件を設けない．
その他
講義資料はT2SCHOLAに掲載する．