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