AIN312 Formal Languages and Automata Theory

Semester        :  2024 Spring
Instructor      :  Ilyas Cicekli  

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

                           Classroom: D8 

 

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

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  Undecidability

14  NP-Completeness

            FINAL

 

 

Lecture Notes:

 

 

Announcements:

 

·       I will use the HADI system ( ( https://hadi.hacettepe.edu.tr/login/ ) for all course announcements. All course materials including your grades will be available in the HADI system.

 

·       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: 18 April 2024, Time: 13:40, Location: D8

o  Midterm will be a closed book exam.