開講通知：形式言語理論

大学院1年の講義「形式言語理論」を下記の通り開講します。

• 日時：2008/04/08（火）1限（8:40-10:10）
• 場所：2203講義室
• 教科書：J.ホップクロフト, R.モトワニ, J.ウルマン「オートマトン 言語理論 計算論I（第2版）」, サイエンス社, ISBN4-7819-1026-2, 2800円
• 教科書の購入：第1回講義の際に、注文を取りまとめます。

通常の講義形式で、ほぼシラバスに従い講義を進めていきますが、講義の進度次第で一部の内容を割愛することがあります。成績判定は、定期試験に代えたレポート課題により行います。

1. 導入、形式言語
2. 決定性有限オートマトン（DFA）
3. 非決定性有限オートマトン（NFA, ε-NFA）とDFA
4. 正則表現
5. 正則表現の応用
6. 正則言語とその性質
7. 有限オートマトンの状態数最小化
8. 文脈自由文法（CFG）
9. 文脈自由文法の応用
10. プッシュダウンオートマトン（PDA）
11. CFGとPDAの等価性
12. 文脈自由言語とその性質
13. 木オートマトンとその応用
14. 木正則表現とその応用