| 授業方針・テーマ |
計算機科学のもっとも基本的な問題の一つである計算とはなにか，言語とはなにかに答えるための道具である基礎的な計算モデルであるオートマトンおよびプログラミング言語や自然言語の基礎となる形式言語理論を学ぶ．計算機のハードウェア，ソフトウェアに関連する多くの分野で用いられており，コンピュータサイエンスに関わる人にとって必須の知識である． |
習得できる知識・能力や授業の
目的・到達目標 |
・離散数学の基礎，「正規言語」および「文脈自由言語」の意味するところを理解する．
・それらの理論が情報検索やコンパイラなどの技術にどのように応用されているのかを知る． |
授業計画・内容
授業方法 |
（授業計画・内容）
01. イントロダクション
02. 有限オートマトン
03. 有限オートマトンの設計
04. 非決定性
05. NFA と DFA の等価性
06. 正規表現
07. 非正規言語
08. 前半のまとめ
09. 文脈自由文法の基礎
10. 文脈自由文法の曖昧性と Chomsky 標準形
11. プッシュダウン・オートマトンの基礎
12. プッシュダウン・オートマトンと文脈自由文法との等価性
13. 非文脈自由言語
14. 発展的話題
15. 後半のまとめ
（授業方法）
教科書をベースにしたスライドを用いて解説する．
|
| 授業外学習 |
資料スライドを事前にkibacoで公開するので、これを用いて予習・復習に役立てる。
|
| テキスト・参考書等 |
教科書
Michael Sipster，計算理論の基礎 [原著第3版] 1.オートマトンと言語. 共立出版（2008）
参考書
John E. Hopcroft, Jeffrey D. Ullman, Rajeev Motwani. オートマトン言語理論計算論＜1＞第2版.サイエンス社（2003）
大川知, 広瀬貞樹, 山本博章. オートマトン・言語理論入門. 共立出版（2012） |
| 成績評価方法 |
小テスト（40%）＋期末試験（60%） |
質問受付方法
(オフィスアワー等) |
オフィスアワーは特に設定しないが、質問や連絡がある場合には随時受け付けるので、onono@tmu.ac.jpまで連絡すること。
|
特記事項
(他の授業科目との関連性) |
関連科目：コンピュータアーキテクチャ基礎論（3年前期）・応用プログラミング実験（3年前期）・計算理論（3年前期）・自然言語処理（3年後期）
|
| 備考 |
|
シラバス照会