| 授業の目標と概要 |
| コンピュータの数学的言語モデルを扱う上で，集合論・言語理論・グラフ理論・論理学・オートマトンなどは，非常 |
| に重要な概念である．本講義では，これまで学んできた集合論・言語理論を土台として，コンピュータの言語モデル |
| とも言えるオートマトンと，プログラミング言語理論の基礎となる論理学について学習する． |
|
| カリキュラムにおける位置づけ |
| 集合・写像・記号理論・グラフ理論，情報数学・離散数学についてあらかじめ勉強しておくことが望ましい． |
|
|
|
| （１）第１階述語論理 |
14 |
| 命題論理 |
|
| 命題論理式の真理値 |
|
| 命題論理と述語論理 |
|
| 第一階述語論理言語 |
|
| 第一階述語論理の推論規則 |
|
| 第一階述語論理における証明 |
|
| 論理の健全性と完全性 |
|
|
|
| （２）正規言語と有限オートマトン |
15 |
| 正規表現と正規言語 |
|
| 文法・BNF・生成木 |
|
| 正規文法と文脈自由文法 |
|
| 決定性オートマトンと非決定性オートマトン |
|
| 有限オートマトンと正規表現の等価性 |
|
| プッシュダウンオートマトン |
|
| 文脈自由文法とプッシュダウンオートマトン |
|
|
|
|
|
|
|
|
|
|
| 教科書 |
|
| 補助教科書 |
|
| 履修上の注意 |
|
集合・写像・記号理論・グラフ理論，情報数学・離散数学について復習しておくこと．小テスト(抜き打ちテスト)を実施するので授業中に行う演習問題は十分理解しておくこと．
|
|
| 評価基準 |
|
定期試験等において，第一階述語論理における証明方法，および，オートマトンに関する基礎知識が身についていることを単位認定の評価基準とする。
|
|
| 評価法 |
|
| 学習・教育目標 |
東京高専 |
|
JABEE |
|
