概要:
本講義では，記号処理を行う機械と，そのような機械によって処理される言語の関係について学ぶ．ここで学ぶ数学的概念はプログラミング言語の設計やコンパイラの構成を行う際の理論的基盤となる．
(科目情報)
教育プログラム 第2学年 ◎科目
授業時間 23.25時間
関連科目 論理数学，情報数学，計算理論，数理論理学(専攻科)
授業の進め方・方法:
原則として毎回，授業内容の理解を問う小テストを実施するので，授業を良く聞いて理解に努めること．
(参考図書)
[1] Sipser, M., Introduction to the Theory of Computation, PWS Pub. Co.
[2] シプサ，M., 計算理論の基礎，共立出版．
[3] ホップクロフト, J. 他，オートマトン 言語理論 計算論 I [第2版]，サイエンス社．
[4] ホップクロフト, J. 他，オートマトン 言語理論 計算論 II [第2版]，サイエンス社．
[5] 川添愛，白と黒のとびら，東京大学出版会．
[6] Stuart, T., アンダースタンディング コンピュテーション，オライリー・ジャパン．
(再試験について)
前期末試験終了後の適切な時期に実施する．受験資格者については試験解説時にアナウンスする．
注意点:
(履修上の注意)
配布プリントを整理するためのクリアファイル(A4サイズ)を用意すること．
(自学上の注意)
参考図書の必要箇所を参照して予習・復習を行うこと．授業内容は [1] に基づく．[2] は [1] の邦訳．[3][4] はこの分野の標準的な教科書の一つ．[5] は形式言語理論を学べるファンタジー小説．[6] はプログラミング (Ruby) を通して実践的に形式言語理論と計算理論を学べる本．
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 4 | 前2,前3,前4,前5,前6,前7,前8,前9,前10,前11,前12,前13,前14,前15,前16 |
| オートマトンの概念について説明できる。 | 4 | 前2,前3,前4,前5,前6,前7,前8,前9,前10,前11 |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | 前2,前3,前4,前5,前6,前7,前8,前9,前10,前11,前12,前13,前14,前15,前16 |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | 前2,前3,前4,前5 |