AIN312 Formal Languages and Automata Theory

AIN312 - Formal Languages and Automata Theory

AIN312 - Formal Languages and Automata Theory, Fridays 13:40 - 16:30. (D10)

Instructor

Lale Özkahya

Office Hours:
Email to arrange an appointment.

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

Similar Courses

MIT Open Courseware: Automata, Computability, and Complexity

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

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

CSCI-E121: Introduction to Theoretical Computer Science by Boaz Barak at Harvard University

Grading (Tentative)

Midterm Exam, 30%

Problem Session Presentation, 30%

Final Exam, 40%

Schedule

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

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

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

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

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

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

5 Official Holiday

6 Context-Free Grammars (CFG’s) and Ambiguity [Slides: 1, 2] Chapter 2.1 (MS)

7 Problem Session 1

8 Midterm Exam

9 Pushdown Automata (PDA) [Slides] Chapter 2.2 (MS)

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

11 Labor Day

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

13 Problem Session 2

14 Problem Session 3

© 2026 Hacettepe University

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