理工学部Faculty of Science and Engineering
COS300XG（計算科学 / Computational science 300）言語の数理Formal Languages
金沢 誠Makoto KANAZAWA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | H9068 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 木3/Thu.3 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目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 | |
| カテゴリー＜理工学部＞Category |
創生科学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
Students learn theories of string and tree languages.
From the discrete structures (DS) area of the standard computer science curriculum J07-CS, the course covers part of the following topics:
DS6: automata and regular expressions
DS7: overview of the theory of computation
The students are expected to master various representations of regular languages and the fundamentals of context-free grammars and of tree automata.
There will be roughly biweekly assignments that the students are required to work on. The time required for study outside of the classes will be at least four hours per week.
The course grade will be based on the assignments (40%) and the final take-home exam (60%).
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
有限オートマトンと文脈自由文法の理論について学ぶ．
カリキュラム標準コンピュータ科学J07-CSのうち，離散構造(DS)エリアからから次のトピックの一部をカバーする。
DS6: オートマトンと正規表現
DS7: 計算論概論
到達目標Goal
・正規言語のいろいろな特徴付けについて理解する．
・文脈自由文法の概念について理解する．
・木オートマトンについて理解する．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
板書を中心とした講義と定期的な課題による。授業の冒頭部分で提出された課題の正答と，実際の間違いの例について解説する。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：有限オートマトン
決定性有限オートマトン(DFA)とその表現，認識可能言語の閉包性
2[対面/face to face]：左商とMyhill-Nerode関係
左商，Myhill-Nerode関係
3[対面/face to face]：Myhill-Nerodeの定理
左商による最小DFAの構成
4[対面/face to face]：正規表現と有限オートマトンの等価性(1)
正規表現，認識可能な言語が正規言語であることの証明
5[対面/face to face]：正規表現と有限オートマトンの等価性(2)
左商を表す正規表現の計算
6[対面/face to face]：正規表現と有限オートマトンの等価性(3)
正規表現の簡略化，左商を表す既簡略の正規表現の個数の有限性
7[対面/face to face]：有限モノイドによる認識(1)
モノイド，DFAの遷移モノイド
8[対面/face to face]：有限モノイドによる認識(2)
有限モノイドによる認識可能言語の特徴づけ，syntactic monoid
9[対面/face to face]：拡張正規表現とstar-free言語
ブール演算に関する閉包性，拡張正規表現，star-free言語
10[対面/face to face]：Schützenbergerの定理
非周期的なものイド，star-free言語からの非周期的なモノイドの構成
11[対面/face to face]：有限木オートマトン(1)
木オートマトン，認識可能な木言語
12[対面/face to face]：有限木オートマトン(2)
認識可能な木言語に対するMyhill-Nerodeの定理
13[対面/face to face]：文脈自由文法
文脈自由言語と認識可能な木言語の関係
14[対面/face to face]：文脈自由言語の性質
Chomsky-Schützenbergerの定理
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】授業中に示された演習問題を解く。
テキスト（教科書）Textbooks
教科書は使用しない。講義ノートを配布する。
参考書References
特に指定しない。
成績評価の方法と基準Grading criteria
定期的に課す演習問題（40％）と期末レポート（60％）の成績で評価する。
学生の意見等からの気づきChanges following student comments
特になし。
その他の重要事項Others
事前に履修すべき科目：離散構造，離散解析