Course Information

Semester	Course Unit Code	Course Unit Title	T+P+L	Credit	Number of ECTS Credits	Last Updated Date
6	AIN312	Formal Languages & Automata Theory	3+0+0	3	6	12.08.2025

Course Details

Language of Instruction	English
Level of Course Unit	Bachelor's Degree
Department / Program	ARTIFICIAL INTELLIGENCE ENGINEERING
Type of Program	Formal Education
Type of Course Unit	Compulsory
Course Delivery Method	Face To Face
Objectives of the Course	The objective of this course is to teach automata and formal language concepts which are important concepts of computer science discipline.
Course Content	Introduction to automata theory. Deterministic finite automata (DFA) and non-deterministic finite automata (NFA). Regular languages and regular expressions. Properties of regular languages and pumping lemma for regular languages. Context-Free languages (CFL) and context-free grammars (CFG). Parse trees. Pushdown automata (PDA). Equivalence of CFG’s and PDA’s. Properties of Context-Free Languages and Pumping Lemma for Context-Free Languages. Turing machines and computability theory.
Course Methods and Techniques	Lecture, Problem Solving
Prerequisites and co-requisities	( BBM102 ) and ( BBM104 )
Course Coordinator	None
Name of Lecturers	Prof. İlyas Çiçekli
Assistants	None
Work Placement(s)	No

Recommended or Required Reading

Resources	1. J.E. Hopcroft, R. Motwani, and J.D. Ullman, ?Introduction to Automata Theory, Languages, and Computation?, 3rd Edition, Addison Wesley, 2007. 2. M. Sipser, ?Introduction to The Theory of Computation?, 3rd Edition, Cengage Learning, 2013.
Course Notes	J.E. Hopcroft, R. Motwani, and J.D. Ullman, “Introduction to Automata Theory, Languages, and Computation”, 3rd Edition, Addison Wesley, 2007. M. Sipser, “Introduction to The Theory of Computation”, 3rd Edition, Cengage Learning, 2013.

Planned Learning Activities and Teaching Methods

Activities are given in detail in the section of "Assessment Methods and Criteria" and "Workload Calculation"

Assessment Methods and Criteria

ECTS Allocated Based on Student Workload

Activities	Quantity	Duration	Total Work Load
Course Duration	14	3	42
Hours for off-the-c.r.stud	14	5	70
Preparation for Midterm Exam	2	15	30
General Exam Preparation	1	20	20
Total Work Load			Number of ECTS Credits 5,4 162

Course Learning Outcomes: Upon the successful completion of this course, students will be able to:

No	Learning Outcomes
1	After completing the course, the students: Learn finite automata and formal language concepts.
2	Learn regular languages and regular expression concepts, and their relationships with finite automata.
3	Learn Pushdown Automata, Context-Free Grammars, and Context-Free Language concepts, and relationships among these concepts.
4	Learn parsing concepts and their relationships with formal language and automata concepts.
5	Learn Turing machines and Type-0 languages.
6	Learn formal language hierarchy and its relationships with computability theory.
7	Learn the importance of formal languages and automata in computer science.
8

Weekly Detailed Course Contents

Week	Topics	Study Materials	Materials
1	ntroduction to Automata Theory and Formal Proofs
2	Deterministic Finite Automata (DFA)
3	Nondeterministic Finite Automata (NFA)
4	Regular Expressions and Regular Languages
5	Properties of Regular Languages and pumping lemma for regular languages
6	Midterm
7	Context-Free Grammars (CFG?s) and Context-Free Languages
8	Parse Trees and Ambiguity
9	Pushdown Automata (PDA)
10	Equivalence of CFG?s and PDA?s.
11	Midterm
12	Properties of Context-Free Languages and Pumping Lemma for Context-Free Languages
13	Turing Machines
14	Undecidability
15	Final exam preparation
16	Final Exam

Contribution of Learning Outcomes to Programme Outcomes

Contribution: 1: Very Slight 2:Slight 3:Moderate 4:Significant 5:Very Significant

https://bilsis.hacettepe.edu.tr/oibs/bologna/progCourseDetails.aspx?curCourse=2733656&lang=en