BBM401 Automata Theory and Formal Languages

Semester        :  Fall 2024
Instructor      :  Ilyas Cicekli  

Email              :  ilyas@cs.hacettepe.edu.tr
Class Hours   :  Thursday 12:40-15:30

                           Classroom: Seminer Hall

Text Book

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

 

Reference Books

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

 

Grading

PopUp Quizzes           : 30%             

Midterm                      : 30%             

Final                            : 40% 

 

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.

https://www.cs.unc.edu/~otternes/comp455/fsm_designer/

 

·       Midterm Date: 14.11.2024 (Thursday), Time: 13:00

o  Midterm will be a closed book exam.