授業科目

オートマトン理論
Automata Theory

担当者

教授   田中 賢
前 水2

単位

2

到達目標

本講義の到達目標は「計算とは何か」を理解することである。オートマトン・言語・アルゴリズムの3つが互いに変換可能な概念であることを知り、コンピュータとその背後にある「計算」の概念を原理的に理解することを目指す。

授業内容

UNIXコマンドの正則表現やコンパイラの構文解析などの実用的な領域から、計算モデルや計算の複雑さなどの理論的領域に至るまで、オートマトン理論は計算機科学のあらゆる分野を支える基礎理論である。オートマトンは、有限の記述を用いて無限の記号列を認識する系であり、この性質が計算機の能力を高い段階に引き上げることに深く関与している。まずこのことを理解し、計算という概念を理論的にとらえていく視点を身につけることが本講義の目的である。演習時間を2回設けるが、演習問題を解くことは理論を確実に理解するための手助けにすぎない。手順を身につけるのではなく、仕組みや理論の意味するところを深く理解するように心がけたい。

授業計画

1、最低限必要な数学的予備知識、語、言語、言語のクラス
2、決定性有限オートマトン
3、非決定性有限オートマトン、ε動作付有限オートマトン、正規表現、UNIXコマンドの正規表現との関連
4、有限オートマトンの簡略化アルゴリズム
5、非正則性とポンプの補題
6、有限オートマトンに関する演習
7、形式文法、チョムスキー階層、文脈自由文法
8、プッシュダウンオートマトン
9、チョムスキー標準形、CKYアルゴリズム、導出木、コンパイラ上の構文解析との関連
10、文法とプッシュダウンオートマトンに関する演習
11、チューリング機械、多テープチューリング機械、計数機械
12、帰納的可算言語、帰納的言語
13、決定問題、停止問題
14、まとめと確認テスト

本講義では毎回の授業に対して予習復習あわせて4時間程度の自己学習が必要である。次回の講義前までに配布資料に目を通し分からない部分を明確にしておくこと。授業後にはその部分を中心に全体の内容を再度確認すること。

授業運営

板書の書き写しよりも講義に耳を傾けることを求める。よって、あらかじめ講義資料を配布し、資料に要点や疑問点を記入していく姿勢で受講されたい。初回に指示するURLより各回分の講義資料をダウンロードし、予習の上講義の際に持参すること。

評価方法

演習問題のレポートと確認テストの点数によって評価する。出席率が2/3に満たないものには単位を与えない。講義は、そのつど質問を促しながら進めていく。よい質問をしたものには加点する。

オフィスアワー

火曜3限 2-217室。会議などで不在の場合があるので電子メールでアポイントをとること。メールアドレスは初回講義で通知する。

使用書

J.ホップクロフト 他『オートマトン 言語理論 計算論 I』第2版[サイエンス社(Information & Computing)]2003年

参考書

J.ホップクロフト 他『オートマトン 言語理論 計算論 II』第2版[サイエンス社(Information & Computing)]2003年
Michael Sipser『計算理論の基礎』初版[共立出版株式会社]2000年

Copyright© 2017 Kanagawa University. All Rights Reserved.