応用形式言語

授業テーマ	言語の形式的な表現方法を理解する。
授業のねらい・到達目標	2年次後学期「オートマトン」に引き続いて，前半は有限オートマトン，正則表現，正則文法の等価性およびそれらの応用を解説する。後半は，文脈自由文法を中心に，言語の形式的な表現方法と構文解析法を解説する。授業時間に余裕があるときには，文脈自由文法とプッシュダウンオートマトンの等価性，属性文法とその応用，言語に関するチョムスキー階層などについても解説する。
授業の方法	講義形式。ときおり演習を行い，宿題を課すこともある。
履修条件	2年次科目「オートマトン」を履修していること。有限オートマトンについては既知として授業を始める。
事前学修・事後学修，授業計画コメント	2年次「オートマトン」の内容とあわせて，各回の授業内容を復習すること。特に，授業で解説した例題を十分に復習し，授業で示した問の解答を検討すること。

授業計画
1	ガイダンス（授業のテーマや到達目標及び授業の方法について説明する）有限オートマトンの復習
2	正則表現
3	正則文法
4	有限オートマトンと正則文法の等価性
5	言語方程式の理論
6	正則文法と正則表現の等価性
7	有限オートマトンや正則表現の応用：字句解析
8	有限オートマトンや正則表現の応用：パターン検索
9	文脈自由文法の基礎概念
10	文脈自由文法の具体例
11	構文木
12	構文木と導出の関係
13	文脈自由文法と言語の曖昧さ
14	文脈自由言語の構文解析法：CKY法
15	文脈自由言語の構文解析法：LL(1)解析法，シフト還元法

その他
教科書	講義ノートと配布資料だけで学習ができるように授業を進める。演習問題集をBlackBoardを介して配布する．
参考書	J. ホップクロフト，R. モトワニ，J．ウルマン『オートマトン言語理論計算論Ⅰ』サイエンス社 2003年第2版 R. モル, A. クフォーリ, M. アービブ『形式言語理論入門』東京電機大学出版局 1995年徳田雄洋『言語と構文解析（情報数学講座 5 ）』共立出版 1995年
成績評価の方法及び基準	試験(100%) 宿題を課すこともある。宿題を課したときには，それも加味しながら総合的に評価する。
オフィスアワー	毎週水曜日１２：１０〜１３：００