AIN312 Formal Languages and

Automata Theory

Semester        :  2025 Spring
Instructor      :  Ilyas Cicekli  

Email              :  ilyas@cs.hacettepe.edu.tr
Class Hours   :  Tuesday 9:40-12:30

                           Classroom: D10 

 

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

2.   M. Sipser, “Introduction to The Theory of Computation”, 3rd  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  Variants of Turing Machines

14  Decidability

            FINAL       

 

Lecture Notes:

·     lec01-introductionToAutomataTheory.pdf

·     lec02-FiniteAutomata.pdf

·     lec03-RegularExpressionsRegularLanguages.pdf

·     lec04-RegularLanguageProperties.pdf

·     lec05-CFG_ContextFreeLanguages.pdf

·     lec06-CFG_ChomskyNormalForm.pdf

·     lec07-PushdownAutomata.pdf

·     lec08-CFLProperties.pdf

·     lec09-TuringMachines.pdf

·     lec10-Decidability.pdf

 

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: April 15, Time: ??, Location: ??

o  Midterm will be a closed book exam.