学部・大学院区分
Undergraduate / Graduate		情報学部
時間割コード
Registration Code		1001049
科目区分
Course Category
専門科目(コンピュータ科)関連専門科目(自然，人社)
科目名　【日本語】
Course Title		[遠隔]オートマトン・形式言語及び演習
科目名　【英語】
Course Title		[remote]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
This course covers the fundamentals of automata and formal language theory. As theories of abstract computing, they provide the theoretical foundation for information processing and serve as essential tools across various disciplines in computer science.
到達目標　【日本語】
Objectives of the Course(JPN)
・オートマトン理オートマトン理論および形式言語理論の基本概念を正しく理解し、体系的に説明できる。
・異なる言語表現（正規表現、文法、オートマトン等）の間の相互変換を理解し、的確に実行できる。
・主要な定理の証明を理解するとともに、それらの論理的手法を応用して、基礎的な問題の証明を行うことができる。
到達目標　【英語】
Objectives of the Course
By the end of this course, students are expected to:
- Understand and articulate the fundamental concepts of automata and formal language theory.
- Comprehend and execute transformations between different language representations.
- Understand the proofs of core theorems and apply these logical techniques to solve and prove basic problems.
授業の内容や構成
Course Content / Plan
オートマトン理論の基本的事項である，オートマトン，正規表現，文脈自由文法，プッシュダウンオートマトンなどを学ぶ。

1. 基本事項の確認
2. 有限オートマトン
3. NFAとDFAの能力の等価性
4. 正規表現とその性質
5. 有限オートマトンの最小化
6. 文脈自由文法
7. プッシュダウンオートマトン
This course covers the fundamental elements of automata theory, including finite automata, regular expressions, context-free grammars, and pushdown automata.

1. Review of Fundamental Concepts
2. Finite Automata
3. Equivalence of NFA and DFA
4. Regular Expressions and Their Formal Properties
5. Minimization of Finite Automata
6. Context-Free Grammars
7. Pushdown Automata
履修条件・関連する科目
Course Prerequisites and Related Courses
「離散数学及び演習」を受講していることが望ましい。
成績評価の方法と基準
Course Evaluation Method and Criteria
演習50％，期末試験50％で評価する。ただし、2回以上の演習課題未提出者、あるいは、期末試験欠席者は「W（欠席）」とする。
Grades are determined based on coursework (50%) and a final examination (50%). However, students will be assigned a grade of "W" (Withdrawal/Absent) if they fail to submit two or more of the assigned exercises or are absent from the final examination.
教科書・参考書
Textbook/Reference book
授業で用いるスライドのハンドアウトをWEB上に用意する。
教科書：J. ホップクロフト／J. ウルマン「オートマトン　言語理論 計算論Ｉ」，野崎明弘ら訳，サイエンス社，ISBN　978-4-7819-1026-X
Handouts (provided in Japanese) will be accessible via tact.
Textbook: John E.Hopcroft, Jeffrey D.Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley.
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)
必要に応じて授業で示す。
授業開講形態等
Lecture format, etc.
授業はオンライン（オンデマンド講義・演習）で実施する。期末試験は対面で行う。
詳細はtact講義ページを通じて通知する。
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)