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

シラバス

GC50201

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

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

概要

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

学習・教育目標

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

授業計画

講義内容
5週 正則表現と有限オートマトン
正則表現、有限オートマトン、非決定性、決定化、閉包、最小化、反復補題
3週 文脈自由文法とプッシュダウンオートマトン
文脈自由文法、プッシュダウンオートマトン、構文解析、あいまいさ、標準形
2週 チューリング機械と計算可能性
チョムスキー階層、チューリング機械、チャーチの提唱、計算可能性、決定問題

教材・参考書等

計算理論の基礎 [原著第2版] 1.オートマトンと言語, M. Sipser著、太田ら訳, 共立出版, 2008

成績評価

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

授業外の学習内容・方法

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

予備知識・前提条件

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

講義のホームページ

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

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

金10:00〜12:00 総合研究棟B-1008

備考

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