計算の理論I
対象：3年生

【JABEE評価基準】
C:計算の理論，情報理論 (3)
  チューリングマシン/オートマトン、言語クラス、文法の相互関係
  を理解している。
C:計算の理論，情報理論 (4)
  与えられた言語または正規文法に基づいて最小の有限オートマトン
  を設計できる。
C:計算の理論，情報理論 (5)
  字句解析および構文解析の基礎を理解している。

【講義概要】
計算の理論Iでは、有限オートマトン、正則表現、文脈自由文法および
プッシュダウンオートマトンについての学習を行う。

【講義内容】
計算の理論では、計算機の理論的なモデルを学習することで、「計算」
に対する理解を深める。計算の理論Iでは、字句解析の基礎となる有
限オートマトンと正規表現について、また、構文解析の基礎となる文
脈自由文法とプッシュダウンオートマトンについて学習し、これらの
相互関係や変換可能性についての理解を目指す。

【教科書】
「オートマトン 言語理論 計算論I [第2版]」
J. ホップクロフト、J. ウルマン、サイエンス社、ISBN4-7819-1026-2

【評価方法】

1. 出席　(20点配点)
出席チェック兼用のミニテストを毎回実施する。
2/3以上出席すること。2/3に満たない場合には放棄とみなす。
遅刻は20分まで。それを超えた場合には欠席として扱う。 

2. レポート　（小×2：各10点配点+中×1：20点配点）
できない場合にも理由を記述の上期日までに必ず提出すること。
提出しない場合には放棄とみなす。 

3. 定期試験　（40点配点）
やむをえない事情で欠席した場合には必ず連絡すること。
連絡なく受けなかった場合には放棄とみなす。 

第01回 04/14 講義内容説明
第02回 04/21 数学的概念と記法
第03回 04/28 言語とオートマトン
  休日 05/05 小レポート：簡単なオートマトン作成
第04回 05/12 決定性有限オートマトン(DFA)と非決定性有限オートマトン(NFA) 
第05回 05/19 DFAとNFAの等価性
第06回 05/26 ε-動作を含むNFA
第07回 06/02 正則（正規）表現
第08回 06/09 正則表現とFAの等価性
第09回 06/16 Myhill-Nerode の定理と最小化
       中レポート：オートマトンの最小化
第10回 06/23 文脈自由文法（CFL)
第11回 06/30 文脈自由文法（CFL)つづき
第12回 07/07 プッシュダウンオートマトン(PDA)
第13回 07/14 PDAつづき
第14回 07/16 (補講)おわりに 
  休日 07/21 小レポート：変換
  試験 07/28 前期定期試験