Course Details

Course Information

Semester	Course Unit Code	Course Unit Title	T+P+L	Credit	Number of ECTS Credits	Last Updated Date
6	COMP306	FORMAL LANGUAGES AND AUTOMATA THEORY	3+2+0	4	6	22.08.2025

Course Details

Language of Instruction	English
Level of Course Unit	Bachelor's Degree
Department / Program	ELECTRICAL-ELECTRONICS ENGINEERING
Type of Program	Formal Education
Type of Course Unit	Compulsory
Course Delivery Method	Face To Face
Objectives of the Course	Develop knowledge for the fundamental concepts in formal languages Learn the techniques used for analyzing and comparing languages and models Develop skills for designing models for computer components
Course Content	The course introduces some fundamental concepts in automata theory and formal languages such as grammar, finite automaton, regular expression, formal language, pushdown automaton, and Turing machine. These concepts form basic models of computation and they are the foundation of many branches in computer science including compiler, software engineering and concurrent systems.
Course Methods and Techniques	Learners will be provided with as much opportunities of hands-on practice as possible with the aim of striking a balance between learner-centeredness and sufficient guidance. Various forms of interaction (i.e. pair work and group work) will also be encouraged to cater for learners with different learning styles. Additionally, individuals will be expected to produce both in-class writings and homework assignments in addition to the reading tasks, which will encourage them to reflect and think critically. Technology will also be incorporated into the classroom procedures in order to create a better learning environment.
Prerequisites and co-requisities	None
Course Coordinator	Associate Prof.Dr. Zafer Aydın zafer.aydin@agu.edu.tr
Name of Lecturers	Asist Prof.Dr. Gülay Yalçın Alkan gulay.yalcin@agu.edu.tr
Assistants	Research Assist. Betül Erkantarcı betul.erkantarci@agu.edu.tr
Work Placement(s)	No

Recommended or Required Reading

Resources	Introduction to the Theory of Computation 3rd Edition by Michael Sipser
Course Notes	....
Documents	...
Assignments	...
Exams	....

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

Veri yok

ECTS Allocated Based on Student Workload

Activities	Quantity	Duration	Total Work Load
Yazılı Sınav	3	30	90
F2F Dersi	14	3	42
Soru Çözümü	14	2	28
Okuma	10	2	20
Total Work Load			Number of ECTS Credits 6 180

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

No	Learning Outcomes
1	Explain the mathematical and algorithmic principles of formal languages
2	Analyze a computational model
3	Design a model for computer components

Weekly Detailed Course Contents

Week	Topics	Study Materials	Materials
1	Finite Automata p1: The mathematical construct of finite automata and the deterministic finite automata (DFA) will be explained and various examples will be given.
2	Finite Automata Part 2: The non-deterministic finite automata (NFA) will be explained and various examples will be given.
3	Finite Automata Part 2: The non-deterministic finite automata (NFA) will be explained and various examples will be given.
4	Regular Languages: Regular Expressions and equivalence with finite automata will be explained. Also, A general look at non-regular languages and the pumping lemma for regular languages will be explained.
5	Context-free Languages, Part 1: Formal definition of a context-free grammar will be given as well as the Chomsky normal form of context-free languages will be discussed.
6	Context-free Languages, Part 1: Formal definition of a context-free grammar will be given as well as the Chomsky normal form of context-free languages will be discussed.
7	Context-free Languages, Part 2: The pushdown automata will be explained and a formal definition of such machines will be given. Also, the non-context-free languages will be discussed briefly.
8	Context-free Languages, Part 3: The pumping lemma for context-free languages will be explained. Also, Deterministic Context-Free Languages will be discussed briefly.
9	Turing Machines, Part 1: The formal definition of Turing machines and some examples of Turing machines will be given. The Church-Turing thesis will be discussed briefly.
10	Turing Machines, Part 2: Turing machine variants like multitape Turing Machines and Nondeterministic Turing Machines will be given and explained.
11	Decidability, Part 1: The concept of the decidability of a problem will be given and explained. Also, decidable regular languages and context-free languages will be investigated.
12	Decidability, Part 2: The concept of undecidability will be explained. The class of undecidable problems will be investigated via several examples.
13	Reducibility, Part 1: Key undecidable problems will be investigated. Methods of reducing problems into other problems will be explained. The formal definition of mapping reducibility will be given and various examples of it will be explained.
14	Complexity Theory: Time complexity will be explained. NP-completeness will be discussed.

Contribution of Learning Outcomes to Programme Outcomes

	P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12
All
C1
C2
C3

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

https://sis.agu.edu.tr/oibs/bologna/progCourseDetails.aspx?curCourse=79041&lang=en

Return to Classes