COSE215: Theory of Computation, 2025 Spring

Course Information

Instructor: Jihyeok Park (박지혁)
- Office: 609A, Science Library Bldg (과학도서관)
- Email: jihyeok_park@korea.ac.kr
Lecture: 13:30–14:45 Mondays and Wednesdays @ 301, Aegineung (애기능생활관)
Teaching Assistant:
Office hours: 14:00–16:00 Tuesdays (by appointment)

Course Materials

Self-contained lecture notes are provided.
Reference: Introduction to Automata Theory, Languages, and Computation (3rd Edition)
Previous Exams
- Midterm: 2023 / 2024
- Final: 2023 / 2024

Installation of Scala and sbt

Scala is a general-purpose programming language combining object-oriented and functional programming in one concise, high-level language. Scala’s static types help avoid bugs in complex applications, and its JVM and JavaScript runtimes let you build high-performance systems with easy access to huge ecosystems of libraries.

The interactive build tool sbt is built for Scala and Java projects.

Please download and install them using the following links:

JDK >= 8 - https://www.oracle.com/java/technologies/downloads/
sbt - https://www.scala-sbt.org/download.html
Scala - https://www.scala-lang.org/download/

Online Automata Simulator

Schedule

#	Date	Title	PDF	Update	Code	Homework
Part 0: Basic Concepts
0	03/05	Course Overview		03/04 (23:39)
1	03/10	Mathematical Preliminaries		03/10 (02:33)
2	03/12	Basic Introduction of Scala		03/12 (13:12)	code	hw01 (by 03/26)
Part 1: Finite Automata
3	03/17	Deterministic Finite Automata (DFA)		03/17 (02:02)	code
4	03/19	Nondeterministic Finite Automata (NFA)		03/18 (22:28)	code
5	03/24	ε-Nondeterministic Finite Automata (ε-NFA)		03/23 (11:36)	code	hw02 (by 04/07)
6	03/26	Regular Expressions and Languages		03/25 (02:40)	code
7	03/31	Equivalence of Regular Expressions and Finite Automata		03/31 (13:02)
8	04/02	Closure Properties of Regular Languages		04/07 (01:38)		ex01
9	04/07	The Pumping Lemma for Regular Languages		04/07 (01:38)		hw03 (by 04/21)
10	04/09	Equivalence and Minimization of Finite Automata		04/08 (00:51)		ex02
Part 2: Pushdown Automata
11	04/14	Context-Free Grammars (CFGs) and Languages (CFLs)		04/14 (01:44)	code
12	04/16	Examples of Context-Free Grammars		04/14 (20:11)
13	04/21	Parse Trees and Ambiguity		04/17 (13:26)
04/23		Midterm Exam	Lectures 1 - 13
14	04/30	Pushdown Automata (PDA)		04/29 (20:13)	code
15	05/05	Examples of Pushdown Automata		05/04 (07:44)		hw04 (by 05/19)
16	05/07	Equivalence of Pushdown Automata and Context-Free Grammars		05/07 (04:10)
17	05/12	Deterministic Pushdown Automata (DPDA)		05/11 (12:43)
18	05/14	Normal Forms of Context-Free Grammars		05/13 (18:32)
19	05/19	Closure Properties of Context-Free Languages		05/21 (15:05)		hw05 (by 06/02)
20	05/21	The Pumping Lemma for Context-Free Languages		05/20 (20:17)
Part 3: Turing Machines / Computability
21	05/26	Turing Machines (TMs)		05/26 (05:24)	code
22	05/28	Examples of Turing Machines		05/27 (02:48)
23	06/02	Extensions of Turing Machines		06/02 (02:48)		hw06 (by 06/16)
24	06/04	The Origin of Computer Science		06/04 (12:34)
25	06/09	Undecidability
26	06/11	P, NP, and NP-Complete Problems
27	06/16	Course Review
06/23		Final Exam	Lectures 14 - 26