Course Introduction and Application Information

Course Code:

COE208

Course Name:

Formal Languages and Automata Theory

Semester:

Fall

Course Credits:

ECTS

Language of instruction:

English

Course Condition:

Does the Course Require Work Experience?:

Type of course:

Compulsory Courses

Course Level:

Bachelor

TR-NQF-HE:6. Master`s Degree

QF-EHEA:First Cycle

EQF-LLL:6. Master`s Degree

Mode of Delivery:

Face to face

Course Coordinator:

Doç. Dr. AMIR SEYYEDABBASI

Course Lecturer(s):

Assist. Prof. Dr. Ali HAMİTOĞLU

Course Assistants:

Course Objective and Content

Course Objectives:

Understand the fundamental concepts and techniques of the theory of computation, including formal languages, grammars, and automata.
Analyze and describe formal languages using mathematical notation and construct automata that recognize or generate these languages.
Apply theoretical concepts to solve problems related to language recognition and generation.
Understand and analyze the limitations of different classes of automata and languages.
Apply the theory of computation to solve problems in fields such as computer science, mathematics, and linguistics.

Course Content:

This course covers the fundamental concepts and techniques of the theory of computation. It covers topics such as g grammar, finite automaton, regular expression, formal language, pushdown automaton, and Turing machine. It provides an in-depth understanding of formal languages, which are mathematical structures that represent sets of strings or sequences of symbols, as well as the automata that recognize and generate these languages. Students will learn how to use mathematical notation to describe languages, and how to construct finite automata, pushdown automata, and Turing machines to recognize or generate languages.

Learning Outcomes

The students who have succeeded in this course;
1) Knows formal languages.
2) Knows calculation models.
3) Can convert regular expressions, grammar and finite state machines.
4) Can convert context-free grammatical and chunky automata to each other.
5) Knows Turing Machines and computability.

Course Flow Plan

Week	Subject	Related Preparation
1)	Introduction and definitions. finite state machine
2)	Finite State Machines (FSM)
3)	Finite State Machines (FSM)
4)	Fundamentals of formal languages - alphabets and languages
5)	Fundamentals of formal languages - Languages and grammars
6)	Fundamentals of formal languages - Chomsky Hierarchy, regular expressions
7)	Deterministic Finite Automata (DFA) - Non-Determinist Finite Automata (NFA)
8)	Midterm
9)	Deterministic Finite Automata (DFA) - Non-Determinist Finite Automata (NFA)
10)	NFA-DFA equivalence
11)	The systematic method of constructing the regular language
12)	Stack-based automata and Context-free languages
13)	Stack-based automata and Context-free languages
14)	Turing Machines

Sources

Course Notes / Textbooks:	Automata Theory, Languages and Computation, by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. (Pearson – 3rd Edition)
References:	Thomson, Introduction to the Theory of Computation, by Michael Sipser (3rd Edition).

Course - Program Learning Outcome Relationship

Course Learning Outcomes	1	2	3	4	5
Program Outcomes

Course - Learning Outcome Relationship

No Effect	1 Lowest	2 Average	3 Highest

Program Outcomes

Level of Contribution

Assessment & Grading

Semester Requirements	Number of Activities	Level of Contribution
Quizzes	2	% 30
Midterms	1	% 30
Final	1	% 40
total		% 100
PERCENTAGE OF SEMESTER WORK		% 60
PERCENTAGE OF FINAL WORK		% 40
total		% 100

Workload and ECTS Credit Calculation

Activities	Number of Activities	Workload
Course Hours	14	42
Study Hours Out of Class	14	42
Homework Assignments	13	26
Midterms	1	15
Final	1	15
Total Workload		140