Course Details

Return to Classes
Course Information
SemesterCourse Unit CodeCourse Unit TitleT+P+LCreditNumber of ECTS CreditsLast Updated Date
6COMP306FORMAL LANGUAGES AND AUTOMATA THEORY3+2+04614.08.2025

 
Course Details
Language of Instruction English
Level of Course Unit Bachelor's Degree
Department / Program COMPUTER 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:
NoLearning 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
WeekTopicsStudy MaterialsMaterials
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 P13 P14 P15
All 5 2 2 4 1 2 2 1 1 1 3 3 4 2 2
C1 5 2 2 3 1 2 2 1 1 1 1 3 4 2 2
C2 5 2 2 3 1 2 2 1 1 1 3 3 4 2 2
C3 5 2 2 4 1 2 1 1 1 1 3 3 4 2 2

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

  
  https://sis.agu.edu.tr/oibs/bologna/progCourseDetails.aspx?curCourse=78330&lang=en
Return to Classes