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

オートマトンと形式言語

このページを印刷する

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

この科目は文理学部（学士(理学)）のディプロマポリシー DP3-5及びカリキュラムポリシー CP3-5に対応している．
・仮説に基づく課題や問題を提示し，客観的な情報を基に，論理的・批判的に考察できる．(A-3-3)
・問題を分析し，複数の解決策を提示した上で，問題を解決することができる．(A-4-3)
・責任と役割を担い，新しい問題に取り組む意識を持ち，そのために必要な情報科学の知識・情報を収集することができる．(A-5-3)
授業の形式 講義
授業の方法 対面授業とする．対面授業にしかるべき理由で参加できない場合はオンラインにて補講を行う．
授業内試験に対しては解答を解説付きでCanvas LMSに公開し，学生へのフィードバックとする．
授業計画
1 有限文字列，決定性オートマトンとその受理言語
【事前学習】論理，集合，写像の諸概念について復習する． （2時間）
【事後学習】有限文字列の数学的取り扱いについて問題を解く． （2時間）
【授業形態】対面授業
2 非決定性オートマトン，決定性オートマトンとの等価性
【事前学習】有限文字列，決定性オートマトンについて復習する． （2時間）
【事後学習】サブセット構成に関する問題を解く． （2時間）
【授業形態】対面授業
3 イプシロン遷移を含むオートマトン，正規表現
【事前学習】非決定性オートマトンに関する各種概念を復習する． （2時間）
【事後学習】イプシロン遷移のやり方を習得し，正規表現に関して問題を解く． （2時間）
【授業形態】対面授業
4 正規言語と有限オートマトンの等価性
【事前学習】正規表現に関して復習する． （2時間）
【事後学習】オートマトンから正規表現への変換を問題練習する． （2時間）
【授業形態】対面授業
5 閉包性，凖同型
【事前学習】正規表現と正規言語に関して復習する． （2時間）
【事後学習】準同型の証明を読んでその構造を理解する． （2時間）
【授業形態】対面授業
6 有限オートマトンのポンプの補題，最小化
【事前学習】正規表現，正規言語と有限オートマトンの等価性について復習する． （2時間）
【事後学習】オートマトンのポンプの補題に関する問題を解く． （2時間）
【授業形態】対面授業
7 Myhill-Nerodeの定理と有限オートマトンのまとめ
【事前学習】ポンプの補題と最小化に関して復習する． （2時間）
【事後学習】有限オートマトン全体を俯瞰して理解を確認する． （2時間）
【授業形態】対面授業
8 文脈自由言語，イプシロン・単項生成除去
【事前学習】正規言語の言語クラスを理解する． （2時間）
【事後学習】文脈自由言語の正規言語との差異を理解する． （2時間）
【授業形態】対面授業
9 チョムスキー標準形とCKY パーサ
【事前学習】文脈自由文法とそのイプシロン・単項除去について復習する． （2時間）
【事後学習】パーサの動作について問題を解く． （2時間）
【授業形態】対面授業
10 文脈自由言語のポンプの補題，プッシュダウンオートマトン
【事前学習】文脈自由言語の受理能力について考察する． （2時間）
【事後学習】プッシュダウンオートマトンの動作について問題を解く． （2時間）
【授業形態】対面授業
11 1-NPDA，グライバッハの標準形
【事前学習】プッシュダウンオートマトンの動作を確認する． （2時間）
【事後学習】1-NPDAおよびGNFへの変換について問題を解く． （2時間）
【授業形態】対面授業
12 1-NPDAとGNFの等価性と文脈自由言語のまとめ
【事前学習】等価性の証明の構造を復習する． （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
成績評価の方法及び基準 授業内テスト:授業内で行う三回の試験（それぞれ40％，40％，20％）を合わせて評価する．(100%)
公的に認められる理由があって授業内試験を受けられなかった場合，再試験を行う．
オフィスアワー e-mailにて随時質問・補講を受け付ける．詳細は授業時に示す．
備考 2年次科目の「離散数学」を履修していることが望ましいが，mustではない．

↑このページのトップ