学部・大学院区分
Undergraduate / Graduate
工学部
時間割コード
Registration Code
0846170
科目区分【日本語】
Course Category
専門科目
科目区分【英語】
Course Category
Specialized Courses
科目名 【日本語】
Course Title
オートマトンと形式言語
科目名 【英語】
Course Title
Automata and Formal Languages
コースナンバリングコード
Course Numbering Code
担当教員 【日本語】
Instructor
佐藤 理史 ○
担当教員 【英語】
Instructor
SATO Satoshi ○
単位数
Credits
2
開講期・開講時間帯
Term / Day / Period
秋 月曜日 3時限
Fall Mon 3
授業形態
Course style
講義
Lecture
学科・専攻【日本語】
Department / Program
電気電子情報工学科
学科・専攻【英語】
Department / Program
Department of Electrical Engineering, Electronics, and Information Engineering
必修・選択【日本語】
Required / Selected
選択
必修・選択【英語】
Required / Selected
Elective


授業の目的 【日本語】
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.
変更する場合は、TACTでアナウンスする。
教科書【英語】
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)