学部・大学院区分
Undergraduate / Graduate		情報学部
時間割コード
Registration Code		1001049
科目区分
Course Category
専門科目(コンピュータ科)関連専門科目(自然，人社)
科目名　【日本語】
Course Title		オートマトン・形式言語及び演習
科目名　【英語】
Course Title		Automata and Formal Languages
コースナンバリングコード
Course Numbering Code		SIS-13-3004-J
担当教員　【日本語】
Instructor		酒井　正彦 ○
担当教員　【英語】
Instructor		SAKAI Masahiko ○
単位数
Credits		3
開講期・開講時間帯
Term / Day / Period		春２期 火曜日 ２時限
春２期 火曜日 ３時限
春２期 火曜日 ４時限
Spring2 Tue 2
Spring2 Tue 3
Spring2 Tue 4
対象学年
Year		２年
2
授業形態
Course style		講義及び演習
開講系（学部）・開講専攻（大学院）
Subject
CS共通
必修・選択
Required / Selected
ＣＳ必修


授業の目的　【日本語】
Goals of the Course(JPN)
オートマトン理論・形式言語理論を学ぶ。これらは抽象的な計算装置の理論であり，情報処理全般の理論的基礎であるとともに，コンピュータ科学の多くの教科における本質的な道具である。
授業の目的　【英語】
Goals of the Course
We study the basics of automata and formal languages, which are fundamental theories of information processing such as automatic operation and data processing.
到達目標　【日本語】
Objectives of the Course(JPN)
オートマトン理論・形式言語理論の理論の基本概念を理解し説明できる。異なる言語の表現間の変換を理解し計算できる。基本的な定理の証明を理解し簡単な問題の証明に応用できる。
到達目標　【英語】
Objectives of the Course
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 Content / Plan
オートマトン理論の基本的事項である，オートマトン，正規表現，文脈自由文法，プッシュダウンオートマトンなどを学ぶ。

1. 基本事項の確認
2. 有限オートマトン
3. NFAとDFAの能力の等価性
4. 正規表現とその性質
5. 有限オートマトンの最小化
6. 文脈自由文法
7. プッシュダウンオートマトン
We learn 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
履修条件・関連する科目
Course Prerequisites and Related Courses
「離散数学及び演習」を受講していることが望ましい。
成績評価の方法と基準
Course Evaluation Method and Criteria
演習50％，期末試験50％で評価する。ただし、2回以上の演習課題未提出者、ならびに、期末試験欠席者は「W（欠席）」とする。
教科書・参考書
Textbook/Reference book
授業で用いるスライドのハンドアウトをWEB上に用意する。
教科書：J. ホップクロフト／J. ウルマン「オートマトン　言語理論 計算論Ｉ」，野崎明弘ら訳，サイエンス社，ISBN　4-7819-0374-X
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.
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)
必要に応じて授業で示す。
授業開講形態等
Lecture format, etc.
nuct講義ページを通じて通知する。
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)