文理学部シラバスTOP > 文理学部 > 情報科学科 > オートマトンと形式言語
日本大学ロゴ

オートマトンと形式言語

このページを印刷する

令和２年度以降入学者 オートマトンと形式言語
令和元年度以前入学者 オートマトンと形式言語
教員名 東条敏
単位数    2 学年 3･4 開講区分 文理学部
科目群 情報科学科
学期 前期 履修区分 選択必修
授業形態 対面授業
Blackboard ID 20231418
授業概要 講義は大きく二部構成とする．第一部は有限オートマトン，正則表現，正則文法の等価性およびそれらの応用を解説する．次の第二部は，文脈自由文法とその標準形，文脈自由文法とプッシュダウンオートマトンの等価性，構文解析法を解説する．最後に文脈依存文法を含むチョムスキー階層とチューリングマシン，計算可能の概念について解説する．
授業のねらい・到達目標 言語の形式的な表現と文法の概念，計算の概念が理解できるようになる．
この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している．

なお，新カリキュラム（令和2年度以降入学者対象）では，この科目は文理学部（学士(理学)）のディプロマポリシー DP3-5及びカリキュラムポリシー CP3-5に対応している．
・仮説に基づく課題や問題を提示し，客観的な情報を基に，論理的・批判的に考察できる．(A-3-3)
・問題を分析し，複数の解決策を提示した上で，問題を解決することができる．(A-4-3)
・責任と役割を担い，新しい問題に取り組む意識を持ち，そのために必要な情報科学の知識・情報を収集することができる．(A-5-3)
授業の形式 講義
授業の方法 対面授業とする．対面授業にしかるべき理由で参加できない場合はオンラインにて補講を行う．
授業内試験に対しては解答を解説付きでBlackboardシステムに公開し，学生へのフィードバックとする．
履修条件 2年次科目の「離散数学」と「グラフ理論」を履修していることが望ましいが，mustではない．
授業計画
1 有限列，決定性オートマトンとその受理言語
【事前学習】集合，関係，写像について復習する． （2時間）
【事後学習】有限文字列と決定性オートマトンに関する問題を解く． （2時間）
【授業形態】対面授業
2 非決定性オートマトン，サブセット構成による決定性・非決定性の等価性
【事前学習】決定性オートマトンに関する各種概念を復習する． （2時間）
【事後学習】サブセット構成に関して問題を解く． （2時間）
【授業形態】対面授業
3 イプシロン遷移を含むオートマトン
【事前学習】決定性/非決定性有限オートマトンとその受理言語に関して復習する． （2時間）
【事後学習】イプシロン除去に関して問題を解く． （2時間）
【授業形態】対面授業
4 正規表現，正規言語と非決定性有限オートマトンとの等価性
【事前学習】イプシロン遷移を含む有限オートマトンに関して復習する． （2時間）
【事後学習】正規表現，正規言語と有限オートマトンに関して問題を解く． （2時間）
【授業形態】対面授業
5 有限オートマトンのポンプの補題
【事前学習】正規表現，正規言語と有限オートマトンの等価性について復習する． （2時間）
【事後学習】オートマトンのポンプの補題に関する問題を解く． （2時間）
【授業形態】対面授業
6 オートマトンの最小化
【事前学習】ポンプの補題に関して復習する． （2時間）
【事後学習】オートマトンの最小化について問題を解く． （2時間）
【授業形態】対面授業
7 有限オートマトンに関するまとめと授業内試験．
【事前学習】正規言語・有限オートマトン全般について復習を行なう． （2時間）
【事後学習】正規言語・有限オートマトン全般について理解の至らなかったところを再度復習する． （2時間）
【授業形態】対面授業
8 文脈自由言語
【事前学習】正規言語・有限オートマトン全般について復習する． （2時間）
【事後学習】正規言語に対する文脈自由言語の特徴を理解する． （2時間）
【授業形態】対面授業
9 CKYパーサ
【事前学習】文脈自由言語の受理能力について考察する． （2時間）
【事後学習】文の解析を行うため，三角表を埋める問題を解く． （2時間）
【授業形態】対面授業
10 文脈自由言語のポンプの補題
【事前学習】CKYパーサについて復習を行なう． （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版
丸岡章 『計算理論とオートマトン言語理論』 サイエンス社 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にて随時質問・補講を受け付ける．詳細は授業時に示す

↑このページのトップ