文学部Faculty of Letters
PHL400BB（哲学 / Philosophy 400）哲学演習（８）Seminar on Philosophy (8)
安東 祐希Yuuki ANDOU
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 文学部Faculty of Letters |
| 添付ファイル名Attached documents | |
| 年度Year | 2024 |
| 授業コードClass code | A2237 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 年間授業/Yearly |
| 曜日・時限Day/Period | 火2/Tue.2 |
| 科目種別Class Type | |
| キャンパスCampus | 市ヶ谷 |
| 教室名称Classroom name | 市BT‐0503 |
| 配当年次Grade | 3～4 |
| 単位数Credit(s) | 4 |
| 備考（履修条件等）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 | 哲学科 |
| 他学科公開科目 | |
| クラスGroup | |
| 昼夜表記Day or Night |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
[Course outline]
This course deals with the theory of formal languages.
[Learning Objectives]
By the end of the course, students should be able to answer the following questions:
-What is the families of formal languages in Chomsky hierarchy?
-What type of automaton corresponds with each family of formal language?
[Learning activities outside of classroom]
Students will be expected to do exercises with many sheets of paper. Your study time will be more than four hours for a class.
[Grading Criteria/Policies]
Final grade will be calculated according to the following process:
Presentation as the person in charge for some parts of the text (60%) and contribution in question-and-answer sections (40%).
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
形式言語について学ぶ。そこでの「言語」とは、文字を並べてできる列の、集まりのことである。どの文字列が入り、どの文字列が入らない、という範囲が定められた集まりである。これを、日常言語を用いた例えで述べてみよう。「わたしはうなぎをたべたことがある」という文字の並びは、日本文として認識できる。一方、「ことあるがたべうなぎわたしたはを」では、いたずら書きにしか見えない。これら二つの文字列を、先頭の一文字目からゆっくりと読んで、あるいは聞いていったとき、われわれの頭はどのように働いてゆくのであろうか。何らかの思い、いわば頭の「状態」が一文字ごとに変わってゆき、最終的に文字列を日本文として認めるか、あるいはどこかの段階でそうではないと棄却する。読み返しながら考え続けるかもしれない。この頭の働きの類似物が、形式言語の理論において活躍する「オートマトン」と呼ばれる機械（的な仕組み）である。
この授業では、いくつかの種類の形式言語と、それらに対応するオートマトンや「文法」について考察する。なお、使用する教科書（１）の本文は、「偉大な魔法使いに弟子入りした平凡な少年」（序文より）の冒険物語として語られている。物語に現れる理論の詳細については、同時に用いる教科書（２）を用いて随時補いながら学んでゆく。
到達目標Goal
次のような概念を理解し、具体例とともに説明できる。
・形式言語を受理する機械
・形式言語を生成する文法
・正則言語、文脈自由言語および文脈依存言語
・チューリングマシン
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」「DP2」「DP3」「DP4」「DP5」に関連
授業で使用する言語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.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：導入
概要説明、教(1):第1章
第2回[対面/face to face]：正則言語
教(1):第2章前半
第3回[対面/face to face]：有限オートマトン
教(1):第2章後半、教(2):3.1
第4回[対面/face to face]：決定性
教(1):第3章前半、教(2):3.2-3
第5回[対面/face to face]：正則表現
教(1):第3章後半、教(2):3.4
第6回[対面/face to face]：機械の例
教(1):第4章前半
第7回[対面/face to face]：機械
教(1):第4章後半
第8回[対面/face to face]：言語のクラス
教(1):第5章前半
第9回[対面/face to face]：文脈自由言語
教(1):第5章後半、教(2):4.1
第10回[対面/face to face]：スタック
教(1):第6章前半、教(2):5.1
第11回[対面/face to face]：pdオートマトン
教(1):第6章後半
第12回[対面/face to face]：「省き」と「延ばし」
教(1):第7章
第13回[対面/face to face]：反復補題
教(1):第8章前半
第14回[対面/face to face]：正則言語でないこと
教(1):第8章後半、教(2):3.5
第15回[対面/face to face]：文法
教(1):第9章前半
第16回[対面/face to face]：文脈自由文法
教(1):第９章後半
第17回[対面/face to face]：cfgとpda
教(1):第10章前半
第18回[対面/face to face]：等価性証明
教(1):第10章後半、教(2):5.2
第19回[対面/face to face]：文脈自由言語再考
教(1):第11章前半
第20回[対面/face to face]：生成規則
教(1):第11章後半
第21回[対面/face to face]：導出木
教(1):第12章前半
第22回[対面/face to face]：統語解析
教(1):第12章後半
第23回[対面/face to face]：文脈依存言語
教(1):第13章前半、教(2):4.4
第24回[対面/face to face]：チューリングマシン
教(1):第13章後半、教(2):6.1
第25回[対面/face to face]：万能Turing機械
教(1):第14章、教(2):7.1
第26回[対面/face to face]：対角線言語
教(1):第15章前半
第27回[対面/face to face]：決定不能性
教(1):第15章後半、教(2):7.2
第28回[対面/face to face]：まとめ
教(1):第16章
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
教科書の問題について、紙に書きながら試行錯誤して自ら解くことを目指し、充分な演習を行うこと。また、発表に際しては、内容を整理して、説明する項目の取捨選択を含めて準備しておくこと。なお、予復習時間の標準は4時間である。
テキスト（教科書）Textbooks
（１）川添愛『白と黒のとびら オートマトンと形式言語をめぐる冒険』（東京大学出版会）2013年
（２）丸岡章『計算理論とオートマトン言語理論［第２版］』（サンエンス社）2021年
参考書References
ホップクロフト／モトワニ／ウルマン（野崎／高橋／町田／山崎 訳）『オートマトン 言語理論 計算論Ⅰ・Ⅱ［第２版］』（サイエンス社）2003年
成績評価の方法と基準Grading criteria
到達目標に関する問題の提示・解題能力を担当箇所の発表内容（60％）において、さらに、目標の問題全般にわたる理解度を他者担当時の質疑応答（40％）において評価する。
学生の意見等からの気づきChanges following student comments
参加者間の議論に使える時間をより多く確保できるよう、工夫したい。
その他の重要事項Others
ゼミの一環として、夏に合宿を行う予定（詳細は年度初めに相談）。