オートマトンと形式言語

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

概要

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

学習・教育目標

キーワード

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

Keywords

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

時間割

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

教材

今年度から教科書を変更しました。(従来の教科書を参考書にして、参考書を教科書にしました。)2つの書籍は内容はほぼ同等ですが、定義や記法に少し違いがあります。
[教科書] 計算理論の基礎[原著第2版] 1.オートマトンと言語, Michael Sipser著, 太田・田中監訳, 共立出版, 2008.
[参考書] オートマトン言語理論 計算論I, J. ホップクロフト,J. ウルマン, R. モトワニ, 第2版, サイエンス社, 2003.

予備知識・前提条件

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

成績評価

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

教員メールアドレス

kam のあとに cs.tsukuba.ac.jp
この授業に関する問い合わせ等は automaton [ at ] logic.cs.tsukuba.ac.jp(教員およびTA)あてに出すこと。

TF・TA

未定。

講義のWebページ

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

オフィスアワー

金曜10:00-12:00、総合研究棟B-1008 (10階)

備考

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