Curriculum

Formal Language and Automata

Instructor

Goal and Theme

  • オートマトンとは何か理解する
  • 有限オートマトンと正規言語の関係を理解する
  • 文脈自由言語についてその特徴・性質を理解する
  • プッシュダウンオートマトンとは何かを理解する
  • チューリングマシンについて理解する

Abstract

この講義は情報科学の様々な側面の基礎をなすオートマトンと形式言語について学ぶ。オートマトンはハードウェアからソフトウェアに至るまでの情報科学の全ての側面において、動作のモデルを定義・表現・設計するたために使われる非常に重要な概念である。講義の前半では、このオートマトンの理解を目標において講義を進める。講義の後半では、そのオートマトンの入力として与えられる形式言語について学ぶ。形式言語の知識ははプログラミング処理系の理解のためには必須である。最後にコンピュータの最も基本的なモデルであるチューリングマシンについても学ぶ。

Schedule

  1. オートマトンとは何か？
  2. 有限オートマトン
  3. 決定性有限オートマトン
  4. 非決定性有限オートマトン
  5. 正規表現
  6. 有限オートマトンと正規表現
  7. 正規言語
  8. 中間試験
  9. 文脈自由文法 (1)
  10. 文脈自由文法 (2)
  11. プッシュダウンオートマトン
  12. 文脈自由文法の性質
  13. チューリングマシン (1)
  14. チューリングマシン (2)
  15. 試験

Materials

配付資料による

References

必要に応じて講義中に紹介するが、以下のいずれかを参考にするとよい。
「オートマトン 言語理論 計算論I (サイエンス社)、J.ホップクロフト他著」
「計算理論の基礎(1)オートマトンと言語(共立出版)、M.Sipser著」

Evaluation Method

中間試験 40%
期末試験 60%

Go to Top