授業の目的 【日本語】
Goals of the Course(JPN) | | この講義では、計算機械やプログラミング言語の基礎となるオートマトンと形式言語の基礎的事項を学び、記号列の無限集合を定義する方法を習得し、計算とは何かについて理解を深めることを目的とする。
この講義を習得することにより、以下のことができるようになることを目標とする。
1. 有限オートマトンと正規文法・正規表現を理解し、それらを定義したり、それらによって定義される記号列集合を求めたり、それら間の相互変換および簡略化を実行できる。
2. プッシュダウンオートマトンと文脈自由文法を理解し、それらを定義したり、それらによって定義される記号列集合を求めたり、それら間の相互変換および簡略化を実行できる。
3. チューリングマシンを理解し、説明できる。
4. チョムスキーの階層を理解し、正規言語と文脈自由言語、および、句構造言語の関係を説明できる。 |
|
|
授業の目的 【英語】
Goals of the Course | | This is an introductory course on automata and formal languages, which is a foundation of computation and programming languages.
The goals of this course are to
1. be able to define an infinite set of strings by automata and formal grammars.
2. be able to obtain an infinite set of strings defined by automata and formal grammars.
3. be able to manipulate automata and formal grammars.
4. be able to understand and explain Turing Machines.
5. be able to understand and explain Chomsky hierarchy. |
|
|
到達目標 【日本語】
Objectives of the Course(JPN)) | | この講義では、計算機械やプログラミング言語の基礎となるオートマトンと形式言語の基礎的事項を学び、記号列の無限集合を定義する方法を習得し、計算とは何かについて理解を深めることを目的とする。
この講義を習得することにより、以下のことができるようになることを目標とする。
1. 有限オートマトンと正規文法・正規表現を理解し、それらを定義したり、それらによって定義される記号列集合を求めたり、それら間の相互変換および簡略化を実行できる。
2. プッシュダウンオートマトンと文脈自由文法を理解し、それらを定義したり、それらによって定義される記号列集合を求めたり、それら間の相互変換および簡略化を実行できる。
3. チューリングマシンを理解し、説明できる。
4. チョムスキーの階層を理解し、正規言語と文脈自由言語、および、句構造言語の関係を説明できる。 |
|
|
到達目標 【英語】
Objectives of the Course | | This is an introductory course on automata and formal languages, which is a foundation of computation and programming languages.
The goals of this course are to
1. be able to define an infinite set of strings by automata and formal grammars.
2. be able to obtain an infinite set of strings defined by automata and formal grammars.
3. be able to manipulate automata and formal grammars.
4. be able to understand and explain Turing Machines.
5. be able to understand and explain Chomsky hierarchy. |
|
|
バックグラウンドとなる科目【日本語】
Prerequisite Subjects | | 離散数学及び演習
計算機プログラミング基礎及び演習
プログラミング及び演習 |
|
|
バックグラウンドとなる科目【英語】
Prerequisite Subjects | | Discrete Mathematics with Exercise
Fundamental Computer Programming with Exercises
Computer Programming with Exercises |
|
|
授業の内容【日本語】
Course Content | | 1. 正規言語
1.1 有限状態オートマトン
1.2 正規文法
1.3 正規表現
2. 文脈自由言語
2.1 プッシュダウンオートマトン
2.2 文脈自由文法
3. チューリングマシン
4. チョムスキーの階層 |
|
|
授業の内容【英語】
Course Content | | 1. Regular languages
1.1 Finite-state automata
1.2 Regular grammars
1.3 Regular expressions
2. Context-free languages
2.1 Pushdown automata
2.2 Context-free grammar
3. Turing Machines
4. Chomsky hierarchy
This course will be taught in Japanese. |
|
|
成績評価の方法と基準【日本語】
Course Evaluation Method and Criteria | | 達成目標に対しての習得度をレポート課題および期末試験にて評価する。
オートマトンと形式言語について、基本的な事項を理解し、定義・解釈・変換操作を正しく実行できれば合格とする。
より難易度の高い問題を解くことができれば、それに応じて成績に反映させる。 |
|
|
成績評価の方法と基準【英語】
Course Evaluation Method and Criteria | | The final grade will be calculated according to the submitted reports and the final examination.
You can pass this lecture if you understand the elemental knowledge about automata and language theory and can define, interpret, and manipulate them. You will get a higher grade if you can solve more difficult problems. |
|
|
履修条件・注意事項【日本語】
Course Prerequisites / Notes | | |
|
履修条件・注意事項【英語】
Course Prerequisites / Notes | | | No requirement for registration. |
|
|
教科書【日本語】
Textbook | | | 岡留剛. 例解図説 オートマトンと形式言語. 森北出版, 2015. |
|
|
教科書【英語】
Textbook | | | Okadome Takeshi. Introduction of Automata and Formal Grammar (in Japanese). Morikita Publisher, 2015. |
|
|
参考書【日本語】
Reference Book | | | Alan P. Parkes. A Concise Introduction to Languages and Machines. Springer, 2008. |
|
|
参考書【英語】
Reference Book | | | Alan P. Parkes. A Concise Introduction to Languages and Machines. Springer, 2008. |
|
|
授業時間外学習の指示【日本語】
Self-directed Learning Outside Course Hours | | 毎回の授業前に教科書の指定個所を読んでおき、よくわからない部分を特定しておくこと。
講義終了時は、復習すること。数回のレポート課題を課すので、それを解いて提出すること。 |
|
|
授業時間外学習の指示【英語】
Self-directed Learning Outside Course Hours | | | Before each session, you should read the designated part of the textbook and identify what you do not understand. After each session, you should review what you studied. For assignments, you should submit reports. |
|
|
使用言語【英語】
Language used | | |
|
使用言語【日本語】
Language used | | |
|
授業開講形態等【日本語】
Lecture format, etc. | | |
|
授業開講形態等【英語】
Lecture format, etc. | | | Sessions are conducted face-to-face in the classroom. |
|
|
遠隔授業（オンデマンド型）で行う場合の追加措置【日本語】
Additional measures for remote class (on-demand class) | | |
|
遠隔授業（オンデマンド型）で行う場合の追加措置【英語】
Additional measures for remote class (on-demand class) | | |
|