学部後期課程
過去（2023年度）の授業の情報です
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2025年4月21日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2025年4月21日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
形式言語理論
正則言語、文脈自由言語、Turing 機械についての基本的な概念と定理を理解する。
正則言語については、有限オートマトンと正則表現の関係、正則言語の性質、Pumping Lemma、Myhill-Nerode の定理、状態数最小有限オートマトン、順序機械、および関連するアルゴリズムについて学ぶ。
文脈自由言語については、文脈自由言語の性質、Pumping Lemma (uvwxy定理）、Ogdenの定理、プッシュダウン・オートマトン、及び関連するアルゴリズムについて学ぶ。
Turing 機械については、Turing 機械の性質、Church のテーゼ、帰納的可算集合と帰納的集合、決定不能な問題について学ぶ。
/
Understand basic concepts and theorems on regular languages, context-free languages, and Turing machines.
For regular languages, study the relationship between finite automata and regular expressions, properties of regular languages, pumping lemma, Myhill-Nerode's theorem, minimum-state finite automata, sequential machines, and related algorithms.
For context-free languages, study properties of context-free grammars, pumping lemma (uvwxy theorem), Ogden's theorem, push-down automata, and related algorithms.
For Turing machines, study properties of Turing machines, Church's thesis, recursively enumerable sets and recursive sets, and undecidable problems.
正則言語については、有限オートマトンと正則表現の関係、正則言語の性質、Pumping Lemma、Myhill-Nerode の定理、状態数最小有限オートマトン、順序機械、および関連するアルゴリズムについて学ぶ。
文脈自由言語については、文脈自由言語の性質、Pumping Lemma (uvwxy定理）、Ogdenの定理、プッシュダウン・オートマトン、及び関連するアルゴリズムについて学ぶ。
Turing 機械については、Turing 機械の性質、Church のテーゼ、帰納的可算集合と帰納的集合、決定不能な問題について学ぶ。
/
Understand basic concepts and theorems on regular languages, context-free languages, and Turing machines.
For regular languages, study the relationship between finite automata and regular expressions, properties of regular languages, pumping lemma, Myhill-Nerode's theorem, minimum-state finite automata, sequential machines, and related algorithms.
For context-free languages, study properties of context-free grammars, pumping lemma (uvwxy theorem), Ogden's theorem, push-down automata, and related algorithms.
For Turing machines, study properties of Turing machines, Church's thesis, recursively enumerable sets and recursive sets, and undecidable problems.
時間割／共通科目コード
コース名
教員
学期
時限
0510002
FSC-IS2002L1
形式言語理論
宮尾 祐介
金曜4限
マイリストに追加
マイリストから削除
講義使用言語
日本語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
可
開講所属
理学部
授業計画
1 基本的定義と記法 / Basic definitions and notations
1.1 関係と部分関数 / Relations and partial functions
1.2 記号列，アルファベット，言語 / String, alphabet, language
2 有限オートマトンと正則言語 / Finite automata and regular languages
2.1 有限オートマトン序章 / Introduction to finite automata
2.2 有限オートマトンの定義 / Definition of finite automata
2.3 非決定性有限オートマトンと決定性有限オートマトンの等価性 / Equivalence of nondeterministic finite automata and deterministic finite automata
2.4 ε動作付非決定性有限オートマトン / Nondeterministic finite automata with ε-transitions
2.5 正則言語のPumping Lemma / Pumping lemma for regular languages
2.6 正則表現 / Regular expressions
2.7 有限オートマトンと正則表現 / Finite automata and regular expressions
2.8 正則言語の性質 / Properties of regular languages
2.9 ブール行列による有限オートマトンの表現 / Expressing finite automata with Boolean matrices
2.10 最小オートマトン / Minimum-state automata
2.11 順序機械 / Sequential machines
2.12 有限オートマトンについてのアルゴリズム / Algorithms for finite automata
3 文脈自由文法 / Context-free grammars
3.1 定義と例 / Definition and examples
3.2 文法の簡素化 / Grammar simplification
3.3 Chomsky 標準形 / Chomsky normal form
3.4 文脈自由言語の性質 / Properties of context-free languages
3.5 文脈自由文法の所属性判定問題 / Membership testing for context-free grammars
3.6 有限オートマトンと正則文法 / Finite automata and regular grammars
4 Turing 機械 / Turing machines
4.1 定義 / Definition
4.2 Turing 機械による関数の計算 / Computing functions by Turing machines
4.3 Turing 機械の変種 / Variants of Turing machines
4.4 Church のテーゼ / Church's thesis
4.5 帰納的可算集合と帰納的集合 / Recursively enumerable sets and recursive sets
4.6 決定不能な問題 / Undecidable problems
授業の方法
講義を中心に行う。
/
Mainly lectures.
成績評価方法
レポート提出状況と期末試験の成績で評価を行う。
/
Evaluation will be based on the submission of reports and the final exam.
教科書
講義の中で配布する。
/
Delivered in the lectures.
参考書
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, (3rd Edition), Addison-Wesley, 2006.
有川節夫，宮野悟，「オートマトンと計算可能性」（第１章，２章，３章），培風館，1986.
履修上の注意
次回の講義内容を予告するので、教科書の該当箇所を予習しておくこと。
/
It is encouraged to read relevant sections of the textbook before the lecture since the contents of the next lecture will be announced.
その他
※初回１回はオンラインとなります。
/
The first lecture will be given online.
