BBM 401 Automata Theory and Formal Languages

Semester : Fall 2025
Instructor : Ilyas Cicekli

Email : ilyas@cs.hacettepe.edu.tr
Class Hours : Wednesday 13:40-16:30

Classroom: Seminer Hall

Text Book

J.E. Hopcroft, R. Motwani, and J.D. Ullman, “Introduction to Automata Theory, Languages, and Computation”, 3^rd Edition, Addison Wesley, 2007.

Reference Books

M. Sipser, “Introduction to The Theory of Computation”, 3^rd Edition, Course Technology, 2013.

Grading

Quizzes : 27%

Attendance : 3%

Midterm : 30%

Final : 40%

Quiz Policy:

· There will be at least 5 pop-up quizzes.

· Pop-up quizzes will NOT be announced; regular attendance is required in order to take the quizzes.

· There are NO make-ups for pop-up quizzes.

· 5% of your quiz grade will be based on your lowest quiz score out of the N quizzes, and 95% will be based on your highest N−1 quiz scores.

Attendance Policy:

· Regular attendance is expected, and 3% of your semester grade will be based on your attendance.

· Attendance will be taken during class hours, and more than one attendance may be recorded on the same day.

Tentative Course Outline:

1 Introduction to Automata Theory and Formal Proofs

2 Deterministic Finite Automata

3 Nondeterministic Finite Automata

4 Regular Expressions and Regular Languages

5 Properties of Regular Languages

6 Context-Free Grammars (CFG’s) and Context-Free Languages

7 Parse Trees and Ambiguity

MIDTERM

8 Pushdown Automata (PDA)

9 Equivalence of CFG’s and PDA’s

10 The Pumping Lemma for Context-Free Languages

11 Properties of Context-Free Languages

12 Turing Machines

13 Turing Machine Variations

14 Undecidability

FINAL

Lecture Notes:

Announcements:

· You can see your grades in the HADI system. ( https://hadi.hacettepe.edu.tr/login/ ).

· You can use the following online Finite State Machine Designer to draw your finite state machines.

· Midterm Date: November 19, Time: ??, Location: ??

o Midterm will be a closed book exam.