【授業の目的】
有限オートマトンとプッシュダウン・オートマトン，及びそれらと双対をなす正規表現と文脈自由文法について学ぶことにより，計算機を用いた情報処理の土台となる計算論的な物の見方・考え方の基礎を身に付けることを目的とする．
【授業の到達目標】
(a) 有限オートマトン，プッシュダウン・オートマトンの設計，及び動作確認が行える．
(b) 正規表現，文脈自由文法の設計，及びそれらの文法を用いた文字列の導出ができる．
(c) 有限オートマトン，プッシュダウン・オートマトン，正規表現，文脈自由文法の表現能力について説明することができる．
【授業概要（キーワード）】
有限オートマトン，プッシュダウン・オートマトン，正規表現，文脈自由文法
【科目の位置付け】
本科目は，情報・エレクトロニクス学科のカリキュラムポリシーの１（２）に記載されている，情報科学，または電気通信工学の応用力を養うための講義となる．また情報数学入門，情報数学Iを基礎とし，さらに計算理論，自然言語処理の基礎となる．
【授業計画】
・授業の方法
講義形式で授業を行う．また理解を深めるために講義時間中に演習問題を行う．
・日程
第１回 イントロダクション
第２回 決定性有限オートマトン
第３回 非決定性有限オートマトン
第４回 決定性と非決定性の等価性
第５回 有限オートマトンの性質
第６回 正規表現
第７回 正規表現と有限オートマトンの等価性
第８回 正規言語の限界
第９回 プッシュダウン・オートマトン
第１０回 文脈自由文法
第１１回 チョムスキー標準系
第１２回 プッシュダウン・オートマトンと文脈自由文法の等価性 その１
第１３回 プッシュダウン・オートマトンと文脈自由文法の等価性 その２
第１４回 文脈自由言語の限界
第１５回 期末試験および講義のまとめ
【学習の方法】
・受講のあり方
講義中に出された小テストによって，理解できていない部分を把握し，復習に努めること．
・授業時間外学習へのアドバイス
毎回行われる小テスト，および講義実施後に公開される資料をもとに復習を行うこと．
【成績の評価】
・基準
授業の到達目標(a)，(b)，(c)それぞれについて，本質的な理解の誤りがないことを合格の基準とする．
・方法
小テスト（20点），期末試験（80点）を合計し，100点満点で判定する．60点以上を合格とする．
【テキスト・参考書】
テキスト：
・丸岡 章，計算理論とオートマトン言語理論，サイエンス社（２００５）
参考書：
・J. ホップクロフト, J. ウルマン, R. モトワニ，オートマトン言語理論 計算論〈1〉第２版，サイエンス社（２００３）
・岩間一雄，オートマトン・言語と計算理論，電子情報通信学会編（２００３）
【その他】
・学生へのメッセージ
講義時間内で理解できない点は，資料をもとに必ず復習を行うこと．特に，定理の言明，定理の証明それぞれについて，自分が理解できているかを確認しながら学習を進めるとよい．
・オフィス・アワー
曜日：金曜日
時間：16:00-17:00
場所：8号館2階 225室
|