AUTOMATA THEORY

BİL565

Course Code: BİL565
Semester: -
Theory+Practice: 3 + 0
ECTS: 10

Course Type

Elective Course

Course Level

Master's Degree Without Thesis

Year of Study

Semester

ECTS

Name of Lecturer(s)

Professor Nizami Gasilov

Learning Outcomes

At the end of this course, the students;

Will be familiar with main concepts such as finite-state automata, pushdown automata and Turing machines in Automata Theory, and regular, context-free and phrase-structure languages in Formal Languages;
Will comprehend abstract models of the computational process and to produce reasoned arguments about the power of these models;
Will be familiar with decidable and undecidable problems, tractable and intractable problems through the abstract notion of automata;
Will have some awareness of the significance of formal models in different areas of Computer Science and Engineering.

Mode of Delivery

Face to face

Prerequisites

Recommended Optional Programme Components

None

Course Description

Introduction to Automata Theory: Problems and Applications. Basic Mathematical concepts and Methods. Alphabets, Strings, Languages, Problems. Deterministic Finite-state Automata. Non-deterministic Finite-state Automata. Regular expressions and languages, Applications. Properties of regular languages. Formal Grammars. Backus-Naur Form. LR grammars. Context-free languages. Pushdown automata. Properties of Context-free languages. Chomsky Normal Form. Turing machines. Application of Turing machines for problem solving. Computations of functions. Uncomputable functions. Unsolvable decision problems. Undecidability and Unsolvability. Computational complexity. Intractable problems. Cellular Automata.

Course Contents

WEEK	TOPICS
1^st Week	Introduction to Automata Theory: Problems and Applications.
2^nd Week	Basic Mathematical concepts and Methods./Alphabets, Strings, Languages, Problems.
3^rd Week	Deterministic Finite-state Automata./Non-deterministic Finite-state Automata.
4^th Week	Regular expressions and languages, Applications. Properties of regular languages.
5^th Week	Formal Grammars.
6^th Week	Backus-Naur Form. LR grammars.
7^th Week	Context-free languages. / Pushdown automata.
8^th Week	Mid-term
9^th Week	Properties of Context-free languages.
10^th Week	Chomsky Normal Form./Turing machines.
11^th Week	Application of Turing machines for problem solving./Computations of functions.
12^th Week	Uncomputable functions. /Unsolvable decision problems.
13^th Week	Undecidability and Unsolvability./Computational complexity.
14^th Week	Intractable problems./Cellular Automata.

Recommended or Required Reading

1. Sudkamp, T.A. (2005) Languages and Machines: an Introduction to the Theory of Computer Science /3E, Addison Wesley.
2. Hopcroft, J.E., Motwani, R., Ullman, J.D. (2006) Introduction to Automata Theory, Languages and Computation /3E, Addison Wesley.
3. Kelley, D. (1995) Automata and Formal Languages: an Introduction, Prentice Hall.

Planned Learning Activities and Teaching Methods

Lecture
Questions/Answers
Presentation
Experiment
Practice
Problem Solving
Project
Report Preparation

Assessment Methods and Criteria

	Quantity	Percentage (%)
Mid-term	1	30
Assignment	1	15
Quiz	1	15
Total(%)		60
Contribution of In-term Studies to Overall Grade(%)		60
Contribution of Final Examination to Overall Grade(%)		40
Total(%)		100

ECTS Allocated Based on Student Workload

Activities	Quantity	Duration (Hour)	Total Workload (Hour)
Midterm exam	1	2	2
Preparation for Quiz
Individual or group work	14	11	154
Preparation for Final exam	1	69	69
Course hours	14	3	42
Preparation for Midterm exam	1	44	44
Laboratory (including preparation)
Final exam	1	2	2
Homework
Total Work Load			313
Total Work Load / 30 (h)			10.43
ECTS Credit of the Course			10

Language of Instruction

Turkish

Work Placement(s)

Programme Qualifications / Learning Outcomes

	LO1	LO2	LO3	LO4
K1	X	X	X
K2		X		X
K3		X	X
K4			X
K5			X
K6		X	X
K7			X
K8		X	X
K9	X		X
K10			X
K11			X
K12			X