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