平成18年度1-2期，2-1期・I113 オートマトンと形式言語(Automata and Formal Languages)@田町キャンパス

本ページは平成18年度1-2期(6月,7月)と2-1期(10月,11月)にJAISTの東京田町キャンパスで 開講されている『I113 オートマトンと形式言語(Automata and Formal Languages)』の 授業のページです．上原は1-1期に石川キャンパスでも同じ授業を担当しています． 石川キャンパスでの授業に関するページはこちらを御覧下さい． 東京田町キャンパスでの授業に関する注意事項は以下の通りです．

• 基本的にはスタジオ撮影したビデオで自習してもらう
• 質問は適宜メール(uehara@jaist.ac.jp)かオフィスアワーに直接受け付ける
• 成績は期末試験での成績で決まる
• ビデオ中で出される演習問題は適宜解いて，理解を深めること

サポート情報

ビデオ中で使用したPowerPointのPDFファイル

• (0)授業内容の説明 (オリジナルサイズ|1/6縮小版)
• (1)数学的準備 (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (2)有限オートマトン(1) (オリジナルサイズ|1/6縮小版)
• (3)有限オートマトン(2) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (4)正則表現 (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (5)正則集合(1) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (6)正則集合(2) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (7)文脈自由文法(1) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (8)文脈自由文法(2) (オリジナルサイズ|1/6縮小版)
• (9)文脈自由文法(3) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (10)プッシュダウンオートマトン(1) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (11)プッシュダウンオートマトン(2) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
  修正スライド^* (オリジナルサイズ|1/6縮小版)
• (12)チューリング機械(1) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (13)チューリング機械(2) (オリジナルサイズ|1/6縮小版)
  演習問題の解答 (オリジナルサイズ|1/6縮小版)
• (14)決定不能性 (オリジナルサイズ|1/6縮小版)

*: (11)プッシュダウンオートマトン(2)の説明中， 以下の二つの点が間違ってました．修正したスライドを公開しておきます．

• スライド中何個所か「到着可能」と書いてあるが，正解は「到達可能」
• 文法をChomsky 標準形に変形する例の中，22枚目の右にある 追加すべき規則にケアレスミスがある．

その他の資料

• 最後に行なう期末試験の難易度の目安になるように， 問題例を公開しておきます．

オフィスアワーの予定

• 未定． 上原は1-2期は別途I222 計算の理論を 担当しているので，この授業の前後に直接聞いて下さい． 2-1期については適宜問い合わせて下さい．

その他

• 2-1期の期末試験は日程は未定です．11月後半になると思います．
• 1-2期は期末試験は9月22,23日に行ないました．

Last modified: Mon Oct 2 13:54:44 JST 2006 by R.Uehara (uehara@jaist.ac.jp)