検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
オートマトンと形式言語
| 令和２年度以降入学者 | オートマトンと形式言語 | ||||
|---|---|---|---|---|---|
| 令和元年度以前入学者 | オートマトンと形式言語 | ||||
| 教員名 | 東条敏 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 前期 | 履修区分 | 選択必修 | ||
| 授業の形態 | 基本は同時双方向型授業（Zoomによるライブ中継）とし，少数回対面授業を行う． BlackboardのコースID：20221447 |
|---|---|
| 授業概要 | 授業第1回めに論理，集合，関数に関する数学的基礎概念の確認したあと，講義は大きく三部構成とする．第一部は有限オートマトン，正則表現，正則文法の等価性およびそれらの応用を解説する．次の第二部は，文脈自由文法とその標準形，文脈自由文法とプッシュダウンオートマトンの等価性，構文解析法を解説する．最後第三部は文脈依存文法を含むチョムスキー階層とチューリングマシン，計算可能の概念について解説する． |
| 授業のねらい・到達目標 | 言語の形式的な表現と文法の概念，計算の概念が理解できるようになる． この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している． なお，新カリキュラム（令和2年度以降入学者対象）では，この科目は文理学部（学士(理学)）のディプロマポリシー DP3-5及びカリキュラムポリシー CP3-5に対応している． ・仮説に基づく課題や問題を提示し，客観的な情報を基に，論理的・批判的に考察できる．(A-3-3) ・問題を分析し，複数の解決策を提示した上で，問題を解決することができる．(A-4-3) ・責任と役割を担い，新しい問題に取り組む意識を持ち，そのために必要な情報科学の知識・情報を収集することができる．(A-5-3) |
| 授業の方法 | 授業の形式：【講義】 同時双方向型授業を中心に授業内演習で理解を深める． 授業内試験に対しては解答を解説付きでBlackboardシステムに公開し，学生へのフィードバックとする． 対面参加できない学生の要件は学部の方針に従う． 対面授業に参加できない人に対してはzoom録画を公開し，履修に充ててもらう． |
| 履修条件 | 2年次科目の「離散数学」と「グラフ理論」を履修していることが望ましい． |
| 授業計画 | |
|---|---|
| 1 |
論理，集合，写像と関数，グラフ理論の基礎について概説する．【対面】
【事前学習】集合，関係，写像について復習する． （2時間） 【事後学習】記号列と言語に関する各種概念を復習する． （2時間） |
| 2 |
有限列，決定性/非決定性有限オートマトンとその受理言語の概念を学ぶ．【同時双方向型】
【事前学習】記号列に関する各種概念を復習する． （2時間） 【事後学習】決定性/非決定性有限オートマトンに関して問題を解く． （2時間） |
| 3 |
サブセット構成による決定性・非決定性の等価性，ε遷移とその除去について学ぶ．【同時双方向型】
【事前学習】決定性/非決定性有限オートマトンとその受理言語に関して復習する． （2時間） 【事後学習】サブセット構成，ε除去に関して問題を解く． （2時間） |
| 4 |
正規表現，正規言語と非決定性有限オートマトンとの等価性について学ぶ．【同時双方向型】
【事前学習】空動作のある有限オートマトンとその受理言語に関して復習する． （2時間） 【事後学習】正規表現，正規言語と有限オートマトンに関して問題を解く． （2時間） |
| 5 |
正規言語と有限オートマトンの閉包特性と凖同型について学ぶ．【同時双方向型】
【事前学習】正規表現，正規言語と有限オートマトンの等価性について復習する． （2時間） 【事後学習】閉包特性と準同型に関する問題を解く． （2時間） |
| 6 |
有限オートマトンのポンプの補題，最小化について学ぶ．【同時双方向型】
【事前学習】閉包特性と準同型について復習する． （2時間） 【事後学習】オートマトンのポンプの補題，最小化について問題を解く． （2時間） |
| 7 |
Myhill-Nerode関係について学ぶ．【同時双方向型】
【事前学習】ポンプの補題，最小化に関して復習する． （2時間） 【事後学習】Myhill-Nerode関係の問題を解く． （2時間） |
| 8 |
正規言語と有限オートマトンについて概括し，授業内テストを行う．【対面】
【事前学習】正規言語・有限オートマトン全般について復習する． （2時間） 【事後学習】正規言語・有限オートマトン全般について理解の至らなかったところを再度復習する． （2時間） |
| 9 |
文脈自由文法，文脈自由言語，チョムスキー標準形を解説する．【同時双方向型】
【事前学習】正規言語の受理能力とその限界について考察する． （2時間） 【事後学習】文脈自由文法，文脈自由言語，チョムスキー標準形に関する問題を解く． （2時間） |
| 10 |
CKYパーサ，文脈自由言語のポンプの補題について学ぶ．【同時双方向型】
【事前学習】文脈自由文法，文脈自由言語，チョムスキー標準形を復習する． （2時間） 【事後学習】CKYパーサ，文脈自由言語のポンプの補題について演習を行う． （2時間） |
| 11 |
プッシュダウンオートマトンと，受理状態の等価性について学ぶ．【同時双方向型】
【事前学習】CKYパーサ，文脈自由言語のポンプの補題を復習する． （2時間） 【事後学習】非決定性プッシュダウンオートマトンに関する問題を解く． （2時間） |
| 12 |
グライバッハの標準形，文脈自由言語と非決定性プッシュダウンオートマトンの等価性について学ぶ．【同時双方向型】
【事前学習】非決定性プッシュダウンオートマトンを復習する． （2時間） 【事後学習】グライバッハの標準形，文脈自由言語と非決定性プッシュダウンオートマトンの等価性について理解を行う． （2時間） |
| 13 |
文脈自由言語の閉包特性と，チョムスキー階層について学ぶ．【同時双方向型】
【事前学習】グライバッハの標準形，文脈自由言語と非決定性プッシュダウンオートマトンの等価性について復習する． （2時間） 【事後学習】文脈自由言語の閉包特性と，チョムスキー階層に関する問題を解く． （2時間） |
| 14 |
チューリングマシンと文脈依存文法について学ぶ．【同時双方向型】
【事前学習】文脈自由言語の閉包特性と，チョムスキー階層について復習する． （2時間） 【事後学習】チューリングマシンと文脈依存文法について問題を解く． （2時間） |
| 15 |
文脈自由言語，文脈依存言語とチューリングマシンについて概括し，授業内テストを行う．【対面】
【事前学習】文脈自由言語，チューリングマシン全般について復習する． （2時間） 【事後学習】文脈自由言語，チューリングマシン全般について理解の至らなかったところを再度復習する． （2時間） |
| その他 | |
|---|---|
| 教科書 | なし |
| 参考書 | Dexter C. Kozen, Automata and Computability, Springer, 1997 ホップクロフト，モトワニ，ウルマン 『言語理論 計算論 I』 サイエンス社 第3版 丸岡章 『計算理論とオートマトン言語理論』 サイエンス社 2021年 第2版 J. E. Hopcroft, R. Motowani, and J.D. Ullman.: Introduction to Automata Theory, Language, and Computation, Addison-Wesley M. Sipser: Introduction to the Theory of Computation, Cengage Learning |
| 成績評価の方法及び基準 | 授業内テスト:中間試験，期末試験，小テスト等を合わせて評価する．(100%) 授業内試験を受けられなかった場合，授業内容に関するレポートを課題として与え，その提出内容によって評価する． |
| オフィスアワー | 遠隔講義につき，e-mailにて随時質問・補講を受け付ける．詳細は授業時に示す |