オートマトンと形式言語

科目名平成29年度以降入学者	オートマトンと形式言語
科目名平成28年度以前入学者	応用形式言語
教員名	戸田誠之助
単位数	2	学年	3	開講区分	文理学部
科目群	情報科学科
学期	前期	履修区分	選択必修

授業概要	前半は有限オートマトン，正則表現，正則文法の等価性およびそれらの応用を解説する．後半は，文脈自由文法を中心に，言語の形式的な表現方法と構文解析法を解説する．授業時間に余裕があるときには，文脈自由文法の標準形，文脈自由文法とプッシュダウンオートマトンの等価性，言語に関するチョムスキー階層などについても解説する．
授業のねらい・到達目標	状態遷移の操作的な定義方法と言語の形式的な表現方法が理解できるようになる．この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています。
授業の方法	講義形式．ときおり演習を行ったり，宿題を課すこともある．本授業の事前・事後学習は,各2時間の学習を目安とする．
履修条件	2年次科目の「離散数学」と「グラフ理論」を履修していること．

授業計画
1	数学的準備【事前学習】集合，関係，写像について復習する．【事後学習】記号列と言語に関する各種概念を理解する．
2	有限オートマトンの直観的モデル【事前学習】記号列に関する各種概念を復習する．【事後学習】有限オートマトンのメカニズムを理解する．
3	有限オートマトンの数学的定義，状態遷移図，状態遷移表【事前学習】有限オートマトンのメカニズムを復習する．【事後学習】計算状況の遷移関係を理解する．
4	正規表現【事前学習】記号列に関する各種概念を復習する．【事後学習】正規表現による言語（正規言語）の表現方法を理解する．
5	正規文法【事前学習】記号列に関する各種概念を復習する．【事後学習】書き換え規則と導出の概念を理解する．
6	有限オートマトン，正規表現，正規文法の等価性（正規表現から有限オートマトンへ；有限オートマトンから正規文法へ）【事前学習】有限オートマトン，正規表現，正規文法の数学的な定義を復習する．【事後学習】正規表現から有限オートマトンを構成する方法，および，有限オートマトンから正規文法を構成する方法を理解する．
7	言語方程式系の理論【事前学習】記号列と言語に関する各種概念を復習する．【事後学習】言語方程式系を解いて正規表現を求める方法を理解する．
8	有限オートマトン，正規表現，正規文法の等価性（有限オートマトンから正規表現へ）【事前学習】正規表現，言語方程式系について復習する．【事後学習】正規文法から言語方程式系を構成する方法，および，言語方程式系を解いて正規表現を求める方法を理解する．
9	有限オートマトンの応用（字句解析）【事前学習】有限オートマトン（特に，状態遷移図）を復習する．【事後学習】字句解析の役割と方法を理解する．
10	正規表現の応用（POSIX拡張正規表現）【事前学習】記号列に関する各種概念を復習する．【事後学習】POSIX拡張正規表現の応用事例と利用方法を理解する．
11	文脈自由文法【事前学習】記号列，言語，形式文法に関する各種概念を復習する．【事後学習】書き換え規則，最左導出，最右導出を理解する．
12	構文木，文法と言語の曖昧さ【事前学習】前回の授業内容と木構造（グラフ理論）について復習する．【事後学習】言語の本質的な曖昧さ，ならびに，構文木・最左導出・最右導出の対応関係を理解する．
13	文脈自由文法の応用：人工言語の構文【事前学習】文脈自由文法と構文木について復習する．【事後学習】プログラミング言語に代表される人工言語の構文が文脈自由文法によって定義されることを理解する．
14	文脈自由言語の構文解析：CYK法【事前学習】記号列，言語，文脈自由文法について復習する．【事後学習】構文解析の役割を理解する．CYK表の数学的な定義とその構成方法を理解する．
15	文脈自由言語の構文解析：シフト還元法【事前学習】記号列，言語，文脈自由文法について復習する．【事後学習】シフト還元動作表の構成方法を理解する．
16	【事前学習】【事後学習】
17	【事前学習】【事後学習】
18	【事前学習】【事後学習】
19	【事前学習】【事後学習】
20	【事前学習】【事後学習】
21	【事前学習】【事後学習】
22	【事前学習】【事後学習】
23	【事前学習】【事後学習】
24	【事前学習】【事後学習】
25	【事前学習】【事後学習】
26	【事前学習】【事後学習】
27	【事前学習】【事後学習】
28	【事前学習】【事後学習】
29	【事前学習】【事後学習】
30	【事前学習】【事後学習】

その他
教科書	講義ノートと配布資料だけで学習できるように授業を進める．演習問題集をBlackboardを介して配布する．ただし，参考書に記載した書籍などを通してより深く学習することを推奨する．
参考書	岡留剛『オートマトンと形式言語入門』森北出版 2018年第1版
成績評価の方法及び基準	試験(100%) 試験は期末試験1回で評価する．宿題を課すこともある．宿題を課したときには，それも加味しながら総合的に評価する．
オフィスアワー	毎週水曜日１２：１０〜１３：００

授業計画
1	数学的準備【事前学習】集合，関係，写像について復習する．【事後学習】記号列と言語に関する各種概念を理解する．
2	有限オートマトンの直観的モデル【事前学習】記号列に関する各種概念を復習する．【事後学習】有限オートマトンのメカニズムを理解する．
3	有限オートマトンの数学的定義，状態遷移図，状態遷移表【事前学習】有限オートマトンのメカニズムを復習する．【事後学習】計算状況の遷移関係を理解する．
4	正規表現【事前学習】記号列に関する各種概念を復習する．【事後学習】正規表現による言語（正規言語）の表現方法を理解する．
5	正規文法【事前学習】記号列に関する各種概念を復習する．【事後学習】書き換え規則と導出の概念を理解する．
6	有限オートマトン，正規表現，正規文法の等価性（正規表現から有限オートマトンへ；有限オートマトンから正規文法へ）【事前学習】有限オートマトン，正規表現，正規文法の数学的な定義を復習する．【事後学習】正規表現から有限オートマトンを構成する方法，および，有限オートマトンから正規文法を構成する方法を理解する．
7	言語方程式系の理論【事前学習】記号列と言語に関する各種概念を復習する．【事後学習】言語方程式系を解いて正規表現を求める方法を理解する．
8	有限オートマトン，正規表現，正規文法の等価性（有限オートマトンから正規表現へ）【事前学習】正規表現，言語方程式系について復習する．【事後学習】正規文法から言語方程式系を構成する方法，および，言語方程式系を解いて正規表現を求める方法を理解する．
9	有限オートマトンの応用（字句解析）【事前学習】有限オートマトン（特に，状態遷移図）を復習する．【事後学習】字句解析の役割と方法を理解する．
10	正規表現の応用（POSIX拡張正規表現）【事前学習】記号列に関する各種概念を復習する．【事後学習】POSIX拡張正規表現の応用事例と利用方法を理解する．
11	文脈自由文法【事前学習】記号列，言語，形式文法に関する各種概念を復習する．【事後学習】書き換え規則，最左導出，最右導出を理解する．
12	構文木，文法と言語の曖昧さ【事前学習】前回の授業内容と木構造（グラフ理論）について復習する．【事後学習】言語の本質的な曖昧さ，ならびに，構文木・最左導出・最右導出の対応関係を理解する．
13	文脈自由文法の応用：人工言語の構文【事前学習】文脈自由文法と構文木について復習する．【事後学習】プログラミング言語に代表される人工言語の構文が文脈自由文法によって定義されることを理解する．
14	文脈自由言語の構文解析：CYK法【事前学習】記号列，言語，文脈自由文法について復習する．【事後学習】構文解析の役割を理解する．CYK表の数学的な定義とその構成方法を理解する．
15	文脈自由言語の構文解析：シフト還元法【事前学習】記号列，言語，文脈自由文法について復習する．【事後学習】シフト還元動作表の構成方法を理解する．
16	【事前学習】【事後学習】
17	【事前学習】【事後学習】
18	【事前学習】【事後学習】
19	【事前学習】【事後学習】
20	【事前学習】【事後学習】
21	【事前学習】【事後学習】
22	【事前学習】【事後学習】
23	【事前学習】【事後学習】
24	【事前学習】【事後学習】
25	【事前学習】【事後学習】
26	【事前学習】【事後学習】
27	【事前学習】【事後学習】
28	【事前学習】【事後学習】
29	【事前学習】【事後学習】
30	【事前学習】【事後学習】