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