Automata and Formal Languages

[GB21601 + GC50201] オートマトンと形式言語 (Automata and Formal Languages)

このページには，筑波大学情報学群情報科学類および情報メディア創成学類で開設している授業『オートマトンと形式言語』に関する情報を置きます。

担当教員: 亀山幸義 (電子メイル: automaton [at] logic.cs.tsukuba.ac.jp)
担当TA (ティーチングアシスタント): 高木 (電子メイル: takaki [at] logic.cs.tsukuba.ac.jp)
曜日・時限: 秋AB 木5-6, 教室 3A202
manabaのページ

連絡事項

[2018/10/20, 重要] 中間試験を11/8 に実施します．詳細は授業で説明します．
[2018/10/01] 履修登録について：この授業は定員(受講者上限)100名としており、 9/28(金)時点までにTWINS で履修申請していた 98名には受講可という連絡をしたところです。まだ、履修申請をしていない人で、この授業を今年度受講したい人は、 automaton[at]logic . cs . tsukuba . ac . jp あてにメイルで、氏名、学籍番号、所属学類を書いて送ってください。先着順で受けつけます。
なお、教職科目履修者など特別な事情がある人は、別枠で受けつけますので申し出てください。
[2018/03/04] このページを作りました。今年度は、テキストを Aho-Hopcroft-Ullmann のものから Sipserのものに変更します。

授業の情報

情報科学類シラバス、情報メディア創成学類シラバス

教科書
- 計算理論の基礎 [原著第２版] １．オートマトンと言語, M. Sipser著、太田ら訳, 共立出版, 2008
授業スケジュール
以下のスケジュールは暫定的であり、若干の変更があり得ます。
- 例題と演習問題は、 manabaシステムのこの授業のページから入手してください。
  第4～7週のいずれかに1回、中間試験をおこないます。
- 第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 あてに出してください。)