オートマトン・形式言語及び演習

更新日:2020-02-26

時間割コード

1001049

ナンバリングコード

SIS-13-3004-J

区分

専門科目(コンピュータ科)
関連専門科目(自然,人社)

単位数

CS必修3単位

開講形態

講義及び演習

対象学年

2年

学期 曜日 時間 集中講義の有無

春2期 月曜2~4限目

講義室

工学部3号館333講義室

開講系

CS共通

担当教員 所属

酒井 正彦

所属

CS・情報システム

メールアドレス

sakai@i.nagoya-u.ac.jp
k-hasimt@i.nagoya-u.ac.jp

オフィスアワー

質問には,講義ならびに演習終了後30分間に対応する。それ以外は事前に時間などを打ち合わせること。

授業概要


◆講義目的

オートマトン理論・形式言語理論とは抽象的な計算装置の理論であり,情報処理全般の理論的基礎であるとともに,コンピュータ科学の多くの教科における本質的な道具である。本講義では,これらの理論の基本概念を理解し説明できること,異なる言語の表現間の変換を理解し計算できること,基本的な定理の証明を理解し簡単な問題の証明に応用できることを目的とする。

◆授業内容

オートマトン理論の基本的事項である,オートマトン,正規表現,文脈自由文法,プッシュダウンオートマトンなどを学ぶ。

1. 基本事項の確認
2. 有限オートマトン
3. NFAとDFAの能力の等価性
4. 正規表現とその性質
5. 有限オートマトンの最小化
6. 文脈自由文法
7. プッシュダウンオートマトン


◆教科書・参考文献・履修条件等

授業で用いるスライドのハンドアウトをWEB上に用意する。「離散数学及び演習」を受講していることが望ましい。
教科書:J. ホップクロフト/J. ウルマン「オートマトン 言語理論 計算論I」,野崎明弘ら訳,サイエンス社,ISBN 4-7819-0374-X

◆授業期間中の課題・宿題等

演習で解いた課題および宿題の解答例をWEB上に掲載し,自習による理解を促す。

成績評価方法・基準

演習の評価30%,中間試験30%,期末試験40%,合計100点満点で60点以上を合格とする。

Course Title

Automata and Formal Languages

Class Timetable Code

1001049

Numbering Code

SIS-13-3004-J

Course Category

Specialized Courses (Department of Computer Science)

Credits

Compulsory [Department of Computer Science]3

Class Format

Lecture and Exercise

Grade

2

Semester, Day and Period

Spring 2 semester Monday2-4

Instructor(s)

SAKAI Masahiko

Affiliation

Department of Computer Science (Computing and Software Systems)

Mailaddress

sakai@i.nagoya-u.ac.jp
k-hasimt@i.nagoya-u.ac.jp

Course Topics


Course Purpose

We study the basics of automata and formal languages, which are fundamental theories of information processing such as automatic operation and data processing. Goal of this class is to understand basic notions of the theory, and be able to explain them, to understand transformations between different languages, and be able to perform them, and to understand proofs of basic theorems, and be able to prove simple problems.

Course Contents

We learn their basics: automata, regular expression, context free grammar, pushdown automata, and so on.

1. Fundamental knowledge
2. Finite automata
3. Equivalence of NFA and DFA
4. Regular expressions and their properties
5. Minimization of finite automata
6. Context free grammar
7. Pushdown automata

Textbooks, Reference Materials and Requirements

Handouts of the slides in the class are found on web.
Textbook: John E.Hopcroft, Jeffrey D.Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley.
This course will be taught in Japanese.

Assignment

Answers of excersises/homeworks are found on web to self-study.

Grading Criteria

Exercises(30%), midterm tests(30%) and examination(40%).