[GB21601 + GC50201] オートマトンと形式言語 (Automata and Formal Languages)
このページには,筑波大学情報学群 情報科学類および情報メディア創成学類 で開設している授業『オートマトンと形式言語』に関する情報を置きます。
担当教員:
亀山幸義
(電子メイル: automaton [at] logic.cs.tsukuba.ac.jp)
担当TA (ティーチングアシスタント): 祁 全羽 (電子メイル: qi [at] logic.cs.tsukuba.ac.jp)
曜日・時限: 秋AB 木5-6, 教室 3A202
manabaのページ
連絡事項
[2019/9/26] 履修登録について: この授業は定員(受講者上限)100名としており、 現時点ですでに100名に到達しています.そこで, 9/29(日)までにTWINS で履修申請した人に受講の優先権を与えます.
なお、教職免許取得など特別な事情がある人は、 別枠で受けつけることがありますので申し出てください。
授業の情報
情報科学類シラバス
、
情報メディア創成学類シラバス
教科書
計算理論の基礎 [原著第2版] 1.オートマトンと言語, M. Sipser著、太田ら訳, 共立出版, 2008
授業スケジュール
以下のスケジュールは暫定的であり、若干の変更があり得ます。
例題と演習問題は、
manabaシステムのこの授業のページ
から入手してください。
第4〜7週のいずれかに中間試験をおこない,最終回に期末試験をおこないます.
第1週: 導入、有限オートマトンと正則表現(1)
授業の導入
アルファベット、文字列、形式言語、正則表現、正則表現が表す言語
数学的帰納法による証明
第2週: 有限オートマトンと正則表現(2)
決定性有限オートマトン(DFA)
第3週: 有限オートマトンと正則表現(3)
非決定性有限オートマトン(NFA)、イプシロン遷移、非決定性
サブセット構成法
第4週: 有限オートマトンと正則表現(4):
正則表現とNFAの対応
DFAの等価性、DFAの最小化
第5週: 有限オートマトンと正則表現(5):
正則言語に対する反復補題
有限オートマトンと正則表現の性質、閉包
第6週: プッシュダウンオートマトンと文脈自由文法(1):
文脈自由文法(CFG)、導出、構文木
プッシュダウンオートマトン(PDA)
第7週: プッシュダウンオートマトンと文脈自由文法(2):
CFGとPDAの対応
チョムスキー標準形
第8週: プッシュダウンオートマトンと文脈自由文法(3):
CYKアルゴリズム
文脈自由文法に対する反復補題
第9週: チューリング機械、授業のまとめ
チューリング機械、計算可能性
様々な決定問題
授業のまとめ
亀山幸義 (kam[at]cs.tsukuba.ac.jp; ただし、この授業に関する連絡は automaton [at] logic.cs.tsukuba.ac.jp あてに出してください。)