コンピュータ科学特論III

授業テーマ	オートマトンと形式言語の発展的な話題，ならびに，計算理論の基礎的な話題。
授業のねらい・到達目標	本学部2年次科目の「オートマトン」ならびに3年次科目の「応用形式言語」の内容を下地に，この授業の前半ではオートマトン・形式言語の発展的な事項を解説する。特に，非正則性の証明，プッシュダウン・オートマトンと文脈自由文法の等価性，非文脈自由性の証明を理解して欲しい。さらに，後半では計算理論の基礎的な事項を解説する。特に，現在のアルゴリズム（計算可能性）の概念がチューリング機械によって定式化されることと，計算不可能な問題が存在することを理解して欲しい。
授業の方法	講義形式で行う。
履修条件	オートマトンと文脈自由文法に関する基礎事項を理解していること。
事前学修・事後学修，授業計画コメント	例題を中心にそれまでの授業内容を十分に復習してくること。

授業計画
1	正則言語の基礎事項（復習）
2	正則言語の反復補題と非正則性の証明
3	右不変同値関係と最小オートマトン
4	文脈自由言語の基礎事項（復習）
5	プッシュダウン・オートマトン
6	文脈自由文法からプッシュダウン・オートマントへ
7	プッシュダウン・オートマントから文脈自由文法へ
8	文脈自由言語の反復補題と非文脈自由性の証明
9	チューリング機械とChurch-Turingの提唱
10	対角線論法
11	停止性判定問題の計算不可能性
12	帰着可能性とその基本的な性質
13	帰着可能性の応用：空集合問題，正則性判定問題，等価性判定問題
14	帰着可能性の応用：ポストの対応問題
15	計算理論における発展的な話題

その他
参考書	Ｊ．ホップクロフト，Ｒ．モトワニ，Ｊ．ウルマン『オートマトン言語理論計算論 I』サイエンス社 2003年第2版 Michael Sipser著／太田和夫他訳『計算理論の基礎（原著第２版）』共立出版 2009年第1版岩田茂樹，笠井琢美『有限オートマトン』森北出版 1991年第1版
成績評価の方法及び基準	レポート(100%)
オフィスアワー	毎週水曜日１２：１０〜１３：００