| 科目名 |
言語処理とオートマトン |
| クラス |
− |
| 授業の概要 |
計算機科学の基礎であるオートマトン理論，形式言語理論の基礎について解説する． |
| 授業の到達目標 |
オートマトン理論は難しいと言われるが，一般に行われる試験は一種の計算問題であり，点をとるだけであればそれほど難しくはない．しかし本当に重要なのは「オートマトンとはそもそも何であるか」という問いである．この授業ではオートマトンおよび形式言語がどういうもので，どう役立つのかを理解することを第一の目標とする． |
| 授業計画 |
１．導入
２．オートマトンとは何か？
３．決定性有限オートマトン
４．非決定性有限オートマトン
５．オートマトンとテキスト検索
６．有限オートマトンの拡張
７．有限オートマトンと正則表現
８．正則表現の簡単化
９．オートマトンの簡単化
１０．文脈自由文法
１１．文脈自由文法の応用
１２．プッシュダウンオートマトン
１３．プッシュダウンオートマトンと文脈自由文法
１４．文脈自由文法の簡単化 |
| テキスト・参考書及び自学自習についての情報 |
テキストは使用しない．参考書については講義時間中に紹介する． |
| 授業の形式 |
講義および演習 |
| 評価の方法（評価の配点比率と評価の要点） |
（１）出席点（４０％）
（２）期末試験（６０％） |
| 本授業に関する情報 |
|
| その他 |
|