授業スケジュール
以下のスケジュールは予定であり、授業の進行状況によって、若干前後するこ
とがあります。2016年度は、受講生の負担を軽減することを目的として、
中間試験と期末試験の2回にわけて試験を行うことにしました。(昨年からの変更点)
- 例題と演習問題は、
manabaシステムのこの授業のページから入手してください。
- 第1週 (10/6): 導入、有限オートマトンと正則表現(1); 教科書 pp.39-60
- アルファベット、文字列、形式言語
- 決定性有限オートマトン(DFA)、遷移表、遷移図、文字列の受理、受理言語
- 数学的帰納法による証明
- short quizの問題と略解はここにあります。
- 第2週 (10/13): 有限オートマトン と正則表現(2): 非決定性有限オートマトン; 教科書 pp.60-75
- 非決定性有限オートマトン(NFA)
- NFAにおける文字列の受理
- サブセット構成法の例
- 第3週 (10/20): 有限オートマトン と正則表現(3): ε遷移をもつオートマトン; 教科書 pp.80-90
- ε遷移(ε動作)
- ε-NFAにおける文字列の受理
- ε遷移の除去
- 第4週 (10/27): 有限オートマトン と正則表現(4): 正則表現
- 正則表現
- 正則表現が表す言語
- 正則表現からε-NFAの導出
- 11/3 は授業はありません。
- 第5週 (11/10): 有限オートマトン と正則表現(5): 正則表現の性質
- 正則言語に対する反復補題
- DFAの状態の同値性の判定
- DFAの等価性、DFAの最小化
- 第6週 (11/17) プッシュダウン・オートマトンと文脈自由文法(1): 文脈自由文法
- 第7週 (11/24): 中間試験
- 11/24, 3A202教室
- 集合 15:15, 試験時間 15:30-17:00の予定
- 試験対象: 第1週から第5週の内容 (第6週の演習までを含み、第6週の文脈自由文法に関する講義は含まない)
- 資料等の持ち込みは不可、ただし、留学生が辞書を持ち込むのは可
(試験問題は、原則として英語でも記述します)
- 第8週 (12/1): プッシュダウン・オートマトンと文脈自由文法(2): プッシュダウンオートマトン
- プッシュダウンオートマトン； 受理状態方式と空スタック方式
- CFG から PDA へ
- 第9週 (12/8): プッシュダウン・オートマトンと文脈自由文法(3): 文脈自由文法の性質と応用
- チョムスキー標準形
- CYKアルゴリズム
- 文脈自由文法に対する反復補題
- 第10週 (12/15): チューリング機械、授業のまとめ
- チューリング機械
- 様々な決定問題
- 応用 (オートマトン/形式言語 と コンピュータサイエンスのかかわり)
- 期末試験 (12/22)
- 15:30-17:00; 期末試験 本体、第6,8-10週の内容
- プラス30分間(17:30まで); 中間試験の復活問題
- 詳細は、manabaシステムの「コースニュース」を参照のこと