オートマトンと形式言語

  [ GB21601 ]
Automata and Formal Languages
対象:3・4学年 開設学期:秋AB 曜日・時限:木5・6 単位数:2単位
担当教員:亀山 幸義

概要

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

学習・教育目標

キーワード

有限オートマトン,プッシュダウンオートマトン、正則言語、文脈自由言語,チューリング機械、計算可能性。

Keywords

Finite Automaton, Pushdown Automaton, Regular Language, Context-free Language, Turing Machine, Computability.

時間割

講義内容/理解すべき項目
第1〜4週有限オートマトンと正則表現
決定性・非決定性オートマトン、正則表現、正則言語、決定手続き、 最小化、閉包性。
第5〜8週プッシュダウン・オートマトンと文脈自由文法
文脈自由文法、文脈自由言語、プッシュダウン・オートマトン、標準形、決定手続き、 閉包性。
第9〜10週チューリング機械と計算可能性
チューリング機械、チャーチの提唱、計算可能性、停止性。

教材

[教科書] オートマトン言語理論 計算論I, J. ホップクロフト,J. ウルマン, R. モトワニ, 第2版, サイエンス社, 2003.
[参考書] 計算理論の基礎[原著第2版] 1.オートマトンと言語, Michael Sipser著, 太田・田中監訳, 共立出版, 2008.

予備知識・前提条件

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

成績評価

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

教員メールアドレス

kam のあとに cs.tsukuba.ac.jp

TF・TA

未定。

講義のWebページ

担当教員のホームページからリンクをたどること。

オフィスアワー

水曜2限 総合研究棟1008

備考

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