検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
オートマトンと形式言語
| 令和元年度以前入学者 | オートマトンと形式言語 | ||||
|---|---|---|---|---|---|
| 平成２８年度以前入学者 | 応用形式言語 | ||||
| 教員名 | 東條敏 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 前期 | 履修区分 | 選択必修 | ||
| 授業の形態 | 基本は同時双方向型授業（Zoomによるライブ中継）とし，少数回対面授業を行う． Blackboard ID：金曜５限→20213033 |
|---|---|
| 授業概要 | 第1回は論理，集合，関数に関する数学的基礎概念の確認，続く6回は有限オートマトン，正則表現，正則文法の等価性およびそれらの応用を解説する．次の5回は，文脈自由文法とその標準形，文脈自由文法とプッシュダウンオートマトンの等価性，構文解析法を解説する．最後3回は文脈依存文法を含むチョムスキー階層とチューリングマシン，計算可能の概念について解説する． |
| 授業のねらい・到達目標 | 言語の形式的な表現と文法の概念，計算の概念が理解できるようになる． この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。 |
| 授業の方法 | 授業の形式：【講義】 講義を中心に授業内演習で理解を深める。 対面授業を行う回は事前に周知し，かつ授業に参加できなかった受講生に対処するため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 |
CKYパーサ，文脈自由言語のポンプの補題について学ぶ．【同時双方向型/対面】
【事前学習】文脈自由言語・文法の概念を復習する． （2時間） 【事後学習】自然言語のパーサ，ポンプの補題に関する例題を解く． （2時間） |
| 10 |
プッシュダウンオートマトンと，受理状態の等価性について学ぶ．【同時双方向型/対面】
【事前学習】パーサのアルゴリズムとポンプの補題を復習する． （2時間） 【事後学習】等価性の証明について演習を行う． （2時間） |
| 11 |
グライバッハの標準形，文脈自由言語と非決定性プッシュダウンオートマトンの等価性について学ぶ．【同時双方向型/対面】
【事前学習】プッシュダウンオートマトンとその受理状態を復習する． （2時間） 【事後学習】非決定性プッシュダウンオートマトンに関する問題を解く． （2時間） |
| 12 |
文脈自由言語の閉包特性と，チョムスキー階層について学ぶ．【同時双方向型/対面】
【事前学習】文脈自由言語とプッシュダウンオートマトンの関係を復習する． （2時間） 【事後学習】オートマトンの計算能力の違いについて理解を行う． （2時間） |
| 13 |
チューリングマシンと文脈依存文法について学ぶ．【同時双方向型/対面】
【事前学習】プッシュダウンオートマトンが受理できない言語について復習する． （2時間） 【事後学習】文脈依存文法が受理する言語に関する問題を解く． （2時間） |
| 14 |
計算の概念と決定可能性，チューリングマシンの停止性について学ぶ．【同時双方向型/対面】
【事前学習】チューリングマシンの概念について復習する． （2時間） 【事後学習】計算の概念，決定可能性について問題を解く． （2時間） |
| 15 |
計算量の概念，非決定性チューリングマシンについて学ぶ．【同時双方向型/対面】
【事前学習】計算の概念，チューリングマシンについて復習する． （2時間） 【事後学習】計算量と，非決定性チューリングマシンについて問題を解く． （2時間） |
| その他 | |
|---|---|
| 教科書 | 使用しない |
| 参考書 | Dexter C. Kozen, Automata and Computability, Springer, 1997 ホップクロフト，モトワニ，ウルマン 『言語理論 計算論 I』 サイエンス社 第3版 マイケル・シプサ 『計算理論の基礎』 共立出版 第3版 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にて随時質問・補講を受け付ける．詳細は授業時に示す |