形式言語とオートマトン2011
授業で使った資料や勉強に役立つ情報を記載します。
知的財産権等に注意を払いながら、有効に活用してください。
平成23年度の授業計画メモ
- 初日(4月19日) 配布資料 ppt
- 第2日目(4月26日) 配布資料 ppt
- 有限オートマトン
- 決定性有限オートマトン
- 非決定性有限オートマトン
- ε-非決定性有限オートマトン
- 第3日目(5月10日) 配布資料 ppt
- 復習
- 正規表現
- 正規表現を有限オートマトンで表現する
- Myhill-Nerodeの定理(紹介だけ。詳細は後日やります。難しいです!)
- 第4日目(5月17日) 配布資料 ppt
- 第5日目(5月24日) ここまでの演習
- 演習と学習効果の確認
- ポンピング定理(補題)とその証明 など (<=後日やります)
- 第6日目(5月28日) 配布資料 ppt
- 簡単な復習
- FAの様相について
- PDA <= 今日の本題
- 第7日目(5月31日) 配布資料 ppt
- 簡単な復習
- Turing Machine (チューリングマシン)
- 第8日目(6月7日) 配布資料 ppt
- Myhill-Nerodeの定理
- その他(Pumping lemma)
- 第9日目(6月14日) 配布資料 ppt
- 第10日目(6月21日) 配布資料 ppt
- 文脈自由言語
- 曖昧性
- 標準形
- その他(埋め込み性など)
- 第11日目(6月25日) 配布資料 ppt
- ここまでのまとめ
- 練習をしましょう!(Chomskyの標準形)
- 第12日目(6月28日) (配布資料は前回と同じ)
- 計算について
- 各種形式文法について
- 練習をしましょう!
- 第13日目(7月5日) 配布資料(過去問+α)
- 第14日目(7月12日)
- 成績評価試験 (注:定期試験期間には試験は実施しません)
(以下、平成21年度の実施状況です!)
- 第5日目(5月25日)
- 第6日目(6月1日)
- 第7日目(6月8日)
- 第8日目(6月15日)(授業あります!)
- 第9日目(6月22日)
- 配布資料 ppt
以下の項目は後日説明します!
- 数学的準備
- 集合・対応・写像(教科書pp.21-26)
- 個数の数え方(1対1写像の存在)
- Cantorの対角線論法(教科書pp.207-208)
- 有限と無限
- 自然数・整数・有理数の個数と実数の個数の比較
- 第10日目(6月29日) 配布資料 ppt
- 文法(言語)の曖昧性
- cfgの標準形
- 構文解析プログラム例
- ポンプの定理の証明 など
- 第11日目(7月6日)
- 配布資料(準備中)
- Prologによる構文解析プログラム
- Progolによる文法獲得 など
- 第12日目(7月13日)配布資料 ppt
- 第13日目(7月20日)(最終日)
- 第14日目(7月27日)(申し訳ありませんが休講です。レポート課題の予定)
- 学期末定期試験
- 実施予定日8月XX日2限?
- 今年の問題も難しいです。論述が中心になります。
例:言語とオートマトンの関係について知るところを1000字程度で述べよ。
試験対策問題集
参考資料等(作成途中)