Information Package / Course Catalogue
Formal Language and Automata Theory
Course Code: CSE205
Course Type: Required
Couse Group: First Cycle (Bachelor's Degree)
Education Language: English
Work Placement: N/A
Theory: 2
Prt.: 2
Credit: 3
Lab: 0
ECTS: 4
Objectives of the Course

This course covers three traditionally central areas of the theory of computation: automata, computability and complexity. It aims to provide the students with an understanding to what are the computation models and to explain what each one can/cannot do, how quickly, and with how much memory. The formal languages and their computation models in the Chomsky hierarchy are introduced. Turing machines are defined and their variants are introduced. Time and space complexity classes are also defined and covered.

Course Content

Regular, context free, and context sensitive languages and their computation models; turing machine and their variants, the definition of algorithm, decidability and undecidability; time and space classes and their relatlions to each other; approximation algorithms and probabilistic algorithms

Name of Lecturer(s)
Prof. İnci ERHAN
Learning Outcomes
1.Have a clear understanding of the Automata theory concepts such as RE's, DFA's, NFA's and their capabilities.
2.Be able to design FAs, NFAs, Grammars, languages modelling.
3.Be able to design sample automata.
4.Have a clear understanding of Turing machines, and their variants.
5.Have a clear understanding of time and space complexity classes and their relations to each other.
Recommended or Required Reading
1.Introduction to the Theory of Computation, by M. Sipser, 2nd Edition, PWS Publishing Company, 2006.
2.Introduction to Automata Theory, Languages and Computation by J. H. Hopcroft, R. Motwani, and J. D. Ullman, 3rd Ed., Addison-Wesley, 2006
Weekly Detailed Course Contents
Week 1 - Theoretical
Basic definitions of Automata, Computability, and Complexity; Mathematical Notions and Terminology; Definitions, Theorems, and Proofs; Types of Proof
Week 2 - Theoretical
Regular Languages 1: Finite Automata ; Nondeterminism
Week 3 - Theoretical
Regular Languages 2: Regular Expressions; Transformation of regular expression into finite automata
Week 4 - Theoretical
Context-Free Languages 1: Context-free Grammars; Chomsky normal form
Week 5 - Theoretical
Context-Free Languages 2: Pushdown Automata; Non-context-free Languages
Week 6 - Theoretical
Turing Machines 1: definition of a Turing machine; Variants of Turing Machines; The Definition of Algorithm
Week 7 - Theoretical
Turing Machines 2: Decidability
Week 8 - Theoretical
Turing Machines 3: Reducibility
Week 9 - Theoretical
Time Complexity 1: Measuring Complexity; Big-O and small-O notation; Analyzing algorithms; Complexity relationships among models
Week 10 - Theoretical
Time Complexity 2: The Class P;The Class NP; NP-completeness
Week 11 - Theoretical
Space Complexity: Savitch's Theorem; The Class PSPACE; The Classes L and NL; NL-completeness; Searching in graphs; NL equals coNL
Week 12 - Theoretical
Intractability: Hierarchy Theorems; Relativization; Circuit Complexity
Week 13 - Theoretical
Approximation Algorithms; Probabilistic Algorithms;
Week 14 - Theoretical
Alternation; Interactive Proof Systems; Parallel Computation
Assessment Methods and Criteria
Type of AssessmentCountPercent
Midterm Examination1%30
Final Examination1%60
Quiz4%10
Workload Calculation
ActivitiesCountPreparationTimeTotal Work Load (hours)
Lecture - Theory141242
Lecture - Practice140228
Quiz4106
Midterm Examination110212
Final Examination110212
TOTAL WORKLOAD (hours)100
Contribution of Learning Outcomes to Programme Outcomes
PÇ-1
PÇ-2
PÇ-3
PÇ-4
PÇ-5
PÇ-6
PÇ-7
PÇ-8
PÇ-9
PÇ-10
PÇ-11
OÇ-1
5
OÇ-2
5
4
4
4
4
OÇ-3
4
5
5
4
4
4
OÇ-4
5
4
4
OÇ-5
4
4
4
Adnan Menderes University - Information Package / Course Catalogue
2026