トップ > カリキュラム > 時間割 > シラバス一覧 > GC50201 オートマトンと形式言語

シラバス

GC50201

オートマトンと形式言語 Automata and Formal Languages

標準履修年次: 3・4年専門・選択 ・2 単位
秋学期AB  木曜日  5・6時限  3A202
担当教員: 亀山 幸義

概要

オートマトンと形式言語は、情報科学の様々な分野に応用をもつ基本的かつ重要な計算モデルである。この授業では、有限オートマトンと正則言語、プッシュダウンオートマトンと文脈自由文法に関する基礎理論を学習する。また、より強力な計算モデルであるチューリング機械と計算可能性の理論について簡単に触れる。

学習・教育目標

  1. 有限オートマトンと正則表現を理解する。
  2. プッシュダウンオートマトンと文脈自由文法を理解する。
  3. チューリング機械などの計算モデルの概要、計算可能性、決定問題を理解する。

授業計画

講義内容
第 1 〜 5週 正則表現と有限オートマトン
正則表現、有限オートマトン、非決定性、閉包、同値、最小化
第 6 〜 8週 文脈自由文法とプッシュダウンオートマトン
文脈自由文法、プッシュダウンオートマトン、構文解析、標準形、閉包
第 9 〜 10週 チューリング機械と計算モデル
チューリング機械、チャーチの提唱、計算モデル、計算可能性、決定問題

教材・参考書等

オートマトン 言語理論 計算論 I [第2版], J. ホップクロフト, R. モトワニ, J. ウルマン 共著, サイエンス社, 2003

成績評価

授業(演習を含む)への出席を前提として、中間試験および期末試験により評価する。

授業外の学習内容・方法

授業で出題する課題および宿題に取り組むこと、また、教科書やハンドアウトのうち、指定された部分を読んで理解しておくこと。

予備知識・前提条件

集合、関係、数学的帰納法などの離散数学の基礎知識。

講義のホームページ

この授業の情報は、 このページに掲載します。

教員連絡先・オフィスアワー

金10:30〜11:30 総合研究棟B-1008

備考

定員100名とする。定員を越える受講希望者がいる場合、 授業ホームページに記載の方法で選抜するので、その指示に従うこと。