理工学部Faculty of Science and Engineering
COT200XE（計算基盤 / Computing technologies 200）形式言語とオートマトンFormal language theory and automata
和佐 州洋Kunihiro WASA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | H6015 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 月4/Mon.4 |
| 科目種別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)
The aim of this course is to help students to understand the basic ideas of the theory of computation. In particular, this course focuses on formal languages and automata. The goal of this course is as follows:
(1) Students can explain the definitions of finite automata and regular language. In addition, students can also explain the relationship between them.
(2) Students can explain the definitions of pushdown automata and context-free language and their relation.
(3) Students can explain the meaning and the proof sketch of pumping lemmata and the Myhill-Nerode theorem.
Before/after each class meeting, students will be expected to spend four hours to understand the course content.
Your overall grade in the class will be decided based on the following
Term-end report: 60%、Mid-term examination: 40%.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
現実にある計算機は様々な機能を持つが，本質的な計算能力は変わらない．本講義では，オートマトンと呼ばれる抽象化した計算機に着目することで，計算の背後にある理論を理解することを目的とする．さらに，プログラミング言語などのように数学的に定義できる文字列の集合（形式言語）が，オートマトンとどのようなかかわりを持つか学ぶ．
到達目標Goal
形式言語とオートマトンに関連したいくつかの概念について，その定義や意味を説明できることを目標とする．具体的には，
- 正規表現と有限オートマトンの関係
- 文脈自由言語とプッシュダウンオートマトンの関係
- 反復補題やMyhill-Nerode の定理
上記についての定義，および，定理の証明の概要を説明できることを目標とする．
授業で使用する言語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]：導入
講義の概要，数学的な背景
第2回[対面/face to face]：決定性有限オートマトン
オートマトンの定義，状態遷移図
第3回[対面/face to face]：正規言語
正規言語の定義，正規言語の性質
第4回[対面/face to face]：非決定性有限オートマトン
非決定性有限オートマトンの定義，決定的と非決定的の違い，正規言語との関係
第5回[対面/face to face]：正規表現とオートマトン
正規表現の定義，正規言語と有限オートマトンの等価性
第6回[対面/face to face]：正規言語に対する反復補題
すべての正規言語がもつ性質
第7回[対面/face to face]：中間試験
前半の内容に関する試験
第8回[対面/face to face]：Myhill-Nerodeの定理
正規言語であるための必要十分条件
第9回[対面/face to face]：文脈自由文法
文脈自由文法の定義，曖昧性，チョムスキー標準形
第10回[対面/face to face]：プッシュダウンオートマトン
プッシュダウンオートマトンの概要と定義，プッシュダウンオートマトンと文脈自由言語の等価性
第11回[対面/face to face]：文脈自由文法に対する反復補題
文脈自由文法が持つ性質
第12回[対面/face to face]：決定的文脈自由言語
決定的文脈自由言語の定義とその性質
第13回[対面/face to face]：チューリングマシン
チューリングマシンの定義とその亜種，決定可能性
第14回[対面/face to face]：まとめ
まとめ
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は4時間を標準とする】各回では，前回までの講義の内容を理解したと仮定して進めるため，その時間をよく確保すること．
テキスト（教科書）Textbooks
教科書は使用しない
参考書References
教科書は指定しないが，本講義はMichael Sipser, Introduction to the Theory of Computation, Third Edition, Cengage Learning, 2013 をベースに授業を構成している．
成績評価の方法と基準Grading criteria
中間試験 (40%)，および，レポート (60%) で評価を行う．本講義の目標に対して，60％以上達成している学生を合格とする．
学生の意見等からの気づきChanges following student comments
本年度授業担当者変更によりフィードバックできません