オートマトン（再履）

授業テーマ	コンピュータサイエンスの基礎理論
授業のねらい・到達目標	有限オートマトンを題材にして、決定性オートマトンと非決定性オートマトンの動作の関係を理解する。さらに有限オートマトンを一般化して計算のモデルであるチューリングマシンについても言及する。
授業の方法	教科書を中心に講義を進める。
履修条件	再履修者用に開講された講義である。
事前学修・事後学修，授業計画コメント	事前学修：前回授業の復習をすること事後学修：各回の内容についてプログラムを作ることが望ましい。

授業計画
1	ガイダンス及びオートマトン概観
2	アルファベット、文字列、言語
3	決定性有限オートマトンの定義
4	決定性有限オートマトンの受理言語
5	決定性有限オートマトンの例と応用
6	非決定性有限オートマトンの定義
7	非決定性有限オートマトンの受理言語
8	非決定性有限オートマトンの例と応用
9	決定性有限オートマトンと非決定性有限オートマトンの等価性
10	ε-動作を含む有限オートマトンの定義と性質
11	有限オートマトンと正則表現の等価性
12	有限オートマトンの反復補題と応用
13	第2回目から第12回目の講義の範囲から任意に出題した課題について回答して、学習内容の確認を行う
14	事前に示した有限オートマトンの課題について，質疑応答及びフィードバックを行う。
15	各種オートマトンとチューリングマシン

その他
教科書	J. ホップクロフト，R. モトワニ，J．ウルマン『オートマトン言語理論計算論Ⅰ』サイエンス社２００３年第２版
成績評価の方法及び基準	授業内テスト(50%)、授業参画度(50%)
オフィスアワー	授業終了後、講師室にて２０分間
備考	教室前方出入口からの無断退席者は減点する場合がある。授業中は特別な場合以外はサングラス不可、脱帽すること。