AIN312 Formal Languages and Automata Theory

AIN312 - Formal Languages and Automata Theory

AIN312 - Formal Languages and Automata Theory, Xdays Y:40 - Z:20. (D?)

Instructor

Lale Özkahya

Office Hours:
Email to arrange an appointment.

All communication will be on https://piazza.com/hacettepe.edu.tr/spring2026/ain312

Resources

Introduction to Automata Theory, Languages, and Computation, by J.E. Hopcroft, R. Motwani, and J.D. Ullman.

Introduction to the Theory of Computation, by Michael Sipser.

Algorithm Design, by Jon Kleinberg and Eva Tardos.

Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

Introduction to Automata Theory, Languages, and Computation, by John E. Hopfcroft, Rajeev Motwani, Jeffrey D. Ullman.

Margaret Fleck and Sariel Har-Peled's automata and formal languages notes, 2008 (available online)

Similar Courses

MIT Open Courseware: Automata, Computability, and Complexity

CS125: Algorithms and Complexity at Harvard Uni.

15-251: Great Theoretical Ideas in Computer Science at Carnegie Mellon Uni.

COS423: Theory of Algorithms at Princeton Uni.

CS170: Efficient Algorithms and Intractable Problems at EECS, Berkeley Uni.

CS374: Algorithms and Models of Computation at Uni. of Illinois

Grading (Tentative)

Midterm Exam, 30%

Problem Session Presentation, 30%

Final Exam, 40%

Schedule

Week Slides/Notes Reading: HMU, MS, İÇ

1 Introduction to Automata Theory and Formal Proofs [Slides: 1, 2] Chapter 0 (MS)

2 Deterministic Finite Automata [Slides] Chapter 1.1 (MS)

3 Nondeterministic Finite Automata [Slides:1, 2] Chapter 1.2 (MS)

4 Regular Languages and Countability [Slides] Chapter 1.3 (MS)

5 Non-regular Languages, Pumping Lemma for Regular Languages [Slides] Chapter 1.4 (MS)

6 Context-Free Grammars (CFG’s) and Ambiguity Chapter 2.1 (MS)

7 Problem Session 1

8 Midterm Exam

9 Pushdown Automata (PDA) Chapter 2.2 (MS)

10 Equivalence of CFG’s and PDA’s, Pumping Lemma for Context-Free Languages Chapter 2.2-3 (MS)

11 Turing Machines, Variants of Turing Machines [Slides 1, 2] Chapter 3.1-2 (MS)

12 Problem Session 2

13 Decidability [Slides] Chapter 4.1 (MS)

14 Problem Session 3

© 2026 Hacettepe University

Week	Slides/Notes	Reading: HMU, MS, İÇ
1	Introduction to Automata Theory and Formal Proofs [Slides: 1, 2]	Chapter 0 (MS)
2	Deterministic Finite Automata [Slides]	Chapter 1.1 (MS)
3	Nondeterministic Finite Automata [Slides:1, 2]	Chapter 1.2 (MS)
4	Regular Languages and Countability [Slides]	Chapter 1.3 (MS)
5	Non-regular Languages, Pumping Lemma for Regular Languages [Slides]	Chapter 1.4 (MS)
6	Context-Free Grammars (CFG’s) and Ambiguity	Chapter 2.1 (MS)
7	Problem Session 1
8	Midterm Exam
9	Pushdown Automata (PDA)	Chapter 2.2 (MS)
10	Equivalence of CFG’s and PDA’s, Pumping Lemma for Context-Free Languages	Chapter 2.2-3 (MS)
11	Turing Machines, Variants of Turing Machines [Slides 1, 2]	Chapter 3.1-2 (MS)
12	Problem Session 2
13	Decidability [Slides]	Chapter 4.1 (MS)
14	Problem Session 3