CS 476: Automata Theory and Formal Languages

Spring 2025

Finite automata, regular expressions, regular languages and their properties, the pumping lemma. Context free grammars and languages, normal forms, pushdown automata, the pumping lemma for the CFLs. Turing machines and their properties. Decidability and undecidable languages. Complexity theory, NP-completeness. Credit units: 3 ECTS Credit units: 5, Prerequisite: CS 201.

Textbook: Introduction to the Theory of Computation, 3rd Edition, Cengage Learning, Michael Sipser

Grading: There will be one midterm exam (25%), a final exam (35%). 3 classworks (10% each), and quizzes (10% total).

Quizzes: At least 10 quizzes.

Classwork will be announced, we expect to hold 3 classworks in total.

Midterm and final exams are closed notes, closed book.

Passing Grade: No predetermined grade to pass the course.

FZ Policy: [(Classworks' Average x 0.3) + (Midterm x 0.25)] should be at least 18 (out of 55).

Makeup Policy: Medical report holders will be entitled for the midterm make up, and ONLY ONE classwork makeup in the last week of the semester. Both midterm and classwork makeups will be comprehensive. We will give no makeups for the quizzes.

Classwork and Exam Schedule:

Midterm
 21.03.2025 (17:45)
Final
 TBD
Classwork 1
 26.02.2025 (17:45)
Classwork 2 09.04.2025 (17:45)
Classwork 3 05.05.2025 (17:45)


Schedule:

Week Section 1 Section 2
1 27 January 2025, Mon (09:00-10:20 block)
29 January 2025, Wed (13:30-15:20)		 27 January 2025, Mon (10:30-12:20)
29 January 2025, Wed (15:30-17:20)
2 05 February 2025, Wed (13:30-15:20)
 05 February 2025, Wed (15:30-17:20)
3 10 February 2025, Mon (08:50-10:20 block)
12 February 2025, Wed (13:30-15:20)		 10 February 2025, Mon (10:30-12:20)
12 February 2025, Wed (15:30-17:20)
4 19 February 2025, Wed (13:30-15:20) 19 February 2025, Wed (15:30-17:20)
5 24 February 2025, Mon (08:50-10:20 block) 24 February 2025, Mon (10:30-12:20)
6 05 March 2025, Wed (13:30-15:20) 05 March 2025, Wed (15:30-17:20)
7

8

9

10

11

12

13

14









Lecture Notes:

Lecture notes below are downloadable only within Bilkent network. Use VPN to access from home.

Week Topic Lecture Notes
1 Introduction 0-intro.pdf
2 Finite Automata 1-dfa.pdf / dfaMod.c
3 Finite Automata 2-nfa.pdf
4 Regular expressions and languages 3-re.pdf
5 Context-free grammars and languages 4-cfg.pdf
6 Context-free grammars and languages  
7 Pushdown Automata 5-pda.pdf
8 Turing Machines 6-tm.pdf
9 Turing Machines  
10 Decidability 7-decidability.pdf
11 Decidability, Reducibility 8-reducibility.pdf
12 Complexity theory and NP-completeness

9-complexity.pdf
13 Complexity theory and NP-completeness  
14 Complexity theory and NP-completeness cook_levin_theorem.pdf

 

Important information for exams and classwork

The following is on the cover pages of your midterm and final exams. Most students do not read this *valuable* information, but everyone SHOULD. These rules apply to the classwork as well:

  1. Write legibly, and make your answers clear.
  2. Provide comprehensible diagrams for state machines (DFA, NFA, PDA, TM).
  3. Unintelligible answers may fail to receive credit.
  4. All proofs should be presented formally, and should follow the styles presented in class.
  5. Handwaving arguments will be considered incorrect.
  6. Ambiguous explanations and proofs will be considered incorrect.
  7. Use notations the same way as described in class.
  8. Closed book, closed notes, no cheat sheets.
  9. NO phones/tablets/laptops etc.

The rules 4 and 5 above point out the fact that this course is a FORMAL, THEORY course. All proofs should be presented as formal expressions, the same way discussed in class. Long paragraphs/sentences of trying to explain a possible answer does not mean that you will receive any credit.