情報科学部Faculty of Computer and Information Sciences
PRI210KA-CS-151（情報学基礎 / Principles of informatics 200）形式言語とオートマトンFormal Language and Automata
藤田 悟
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | J0512 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 水2/Wed.2 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 / Koganei |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | ○ |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) |
（１） 受講希望者 (受講検討中の者も含む) は、情報科学部学部Googleフォーム（https://forms.gle/ECvwxVe2NcxmrbTK9）で初回講義前までに希望申請をしてください。（※以下URLのご案内があるGoogleフォームとは異なるのでご注意ください。） （２） 以下のURLと教育開発支援機構事務局の案内に従って、履修希望の申請を行ってください。 https://www.hoseikyoiku.jp/risyu/index.html （３） 履修取消については、ご自身の所属学部の履修取消期間内に必ず同時に履修削除を行ってください。 |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | ○ |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| 選択・必修Optional/Compulsory | |
| カテゴリー（2022年度以降入学者）Category (2022~) | |
| カテゴリー（2021年度以前入学者）Category (~2021) | |
| カテゴリーCategory |
専門教育科目 専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
This course covers fundamental notions in formal language theory, including automata, relationship between finite automata and regular languages, characteristics and properties of context-free languages, pushdown automata and Turing machines.
The goal of this course is to understand fundamental notions in formal language theory. Namely, students will be able to
1. construct and show configurations of finite state automata, pushdown automata and Turing machines
2. explain and construct languages generated by regular and context-free grammars
Before each class, students will be expected to have read relevant chapter(s) from the text. During the class, students are expected to confirm their understandings.
Students will be studying four hours for a class.
Grading will be decided based on term-end exam (60%) and in class tests including mid-term exam (40%).
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
・オートマトンとは何か理解する
・有限オートマトンと正規言語の関係を理解する
・文脈自由言語についてその特徴・性質を理解する
・プッシュダウンオートマトンとは何かを理解する
・チューリングマシンについて理解する
到達目標Goal
オートマトン、形式言語の基本的な枠組みについて理解する。具体的には、
１）有限状態オートマトン・プッシュダウンオートマトンの時点表示・構成ができること
２）文脈自由文法が生成する言語・文法を説明・構成できること
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち「DP2」と「DP4-1」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
この講義は情報科学の様々な側面の基礎をなすオートマトンと形式言語について学ぶ。オートマトンはハードウェアからソフトウェアに至るまでの情報科学の全ての側面において、動作のモデルを定義・表現・設計するたために使われる非常に重要な概念である。講義の前半では、このオートマトンの理解を目標において講義を進める。講義の後半では、そのオートマトンの入力として与えられる形式言語について学ぶ。形式言語の知識はプログラミング言語やその処理系の理解のために必須のものである。
なお、毎回の講義では、説明のなかで30分程度を小テストに充てる。授業で課した課題(小テストやレポート)等を取り上げ、授業内で全体に対してフィードバックを行う。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：序論
1.オートマトンとは計算機のモデル
2.形式言語は言語のモデル
3.オートマトンと形式言語の関係
4.チョムスキー階層
5.オートマトンの応用
第2回[対面/face to face]：有限オートマトン(1)
1.オートマトンの状態遷移図表現
2.集合
3.五字組表現
第3回[対面/face to face]：有限オートマトン（2）
1.有限オートマトンの例
2.様相、受理・拒否
第4回[対面/face to face]：有限オートマトン（3）
1.有限オートマトン演習
第5回[対面/face to face]：非決定性有限オートマトン(1)
1.決定性オートマトンと非決定性オートマトン
2.非決定性オートマトンの状態遷移図
3.非決定性オートマトンの五字組表現
第6回[対面/face to face]：非決定性有限オートマトン(2)
1.空動作を伴うオートマトン
2.空動作を伴うオートマトンの状態遷移図
3.空動作を伴うオートマトンの五字組表現
4.決定性オートマトンと非決定性オートマトンの同等性
5.正規表現から非決定性オートマトンに
6.決定性オートマトンの最簡形
第7回[対面/face to face]：中間試験
有限オートマトンのまとめ
主にオートマトンの部分について試験を行う
第8回[対面/face to face]：プッシュダウンオートマトン
1.決定性プッシュダウンオートマトン
2.決定性プッシュダウンオートマトンの七字組表現
3.決定性プッシュダウンオートマトンの動作
4.決定性プッシュダウンオートマトンの状態遷移図
5.非決定性プッシュダウンオートマトン
6.非決定性プッシュダウンオートマトンの七字組表現
7.非決定性プッシュダウンオートマトンの動作
8.非決定性プッシュダウンオートマトンの状態遷移図
第9回[対面/face to face]：チューリングマシン(1)
1. 決定性チューリングマシン
第10回[対面/face to face]：チューリングマシン(2)
1.非決定性チューリングマシン
第11回[対面/face to face]：文法(1)
1.正規文法
2.言語の生成装置としての形式文法
3.オートマトンと文法の対比・階層性
4.文脈自由文法
第12回[対面/face to face]：文法(2)
1.文法の種類
2.文脈自由文法の例
3.文脈自由文法と木構造
4.2分木からチョムスキー標準形に
5.文脈依存文法
第13回[対面/face to face]：文法(3)
1.文法演習
第14回[対面/face to face]：オートマトンと形式言語の関係およびまとめ
正規文法と有限オートマトンの関係
1.正規表現による正規言語の表現
2.有限オートマトンで表現できない文脈自由文法
3.閉包性
4.チョムスキー標準形
5.グライバッハ標準形
１－14回の講義のまとめ
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
教科書の内容をよく読んでおくこと。講義では、正しく理解しているかどうか確認を行うようにする。
本授業の準備・復習時間は、計週4時間を標準とする。
テキスト（教科書）Textbooks
米田、広瀬、大里、大川著「オートマトン・言語理論の基礎」近代科学社
参考書References
J.ホップクロフト他著「オートマトン 言語理論 計算論I」サイエンス社
富田、横森著「オートマトン・言語理論」森北出版
成績評価の方法と基準Grading criteria
授業内諸テスト、課題で40％。期末試験で60%。
学生の意見等からの気づきChanges following student comments
演習を豊富に実施する
その他の重要事項Others
本講義は複数クラスで内容を統一し、講義内容・教材を担当教員で共同で用意している。また、その内容は担当教員の一人の企業でのプログラミング言語の研究開発の経験に基づく形式言語とオートマトンに関する講義である。