TYPE OF COURSE UNIT	Elective Course
LEVEL OF COURSE UNIT	Master's Degree With Thesis
YEAR OF STUDY	-
SEMESTER	-
NUMBER OF ECTS CREDITS ALLOCATED	10
NAME OF LECTURER(S)	Professor Nizami Gasilov
LEARNING OUTCOMES OF THE COURSE UNIT	At the end of this course, the students; 1) 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; 2) Will comprehend abstract models of the computational process and to produce reasoned arguments about the power of these models; 3) Will be familiar with decidable and undecidable problems, tractable and intractable problems through the abstract notion of automata; 4) Will have some awareness of the significance of formal models in different areas of Computer Science and Engineering.
MODE OF DELIVERY	Face to face
PRE-REQUISITES OF THE COURSE	No
RECOMMENDED OPTIONAL PROGRAMME COMPONENT	None
COURSE DEFINITION	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 1st Week Introduction to Automata Theory: Problems and Applications. 2nd Week Basic Mathematical concepts and Methods./Alphabets, Strings, Languages, Problems. 3rd Week Deterministic Finite-state Automata./Non-deterministic Finite-state Automata. 4th Week Regular expressions and languages, Applications. Properties of regular languages. 5th Week Formal Grammars. 6th Week Backus-Naur Form. LR grammars. 7th Week Context-free languages. / Pushdown automata. 8th Week Mid-term 9th Week Properties of Context-free languages. 10th Week Chomsky Normal Form./Turing machines. 11th Week Application of Turing machines for problem solving./Computations of functions. 12th Week Uncomputable functions. /Unsolvable decision problems. 13th Week Undecidability and Unsolvability./Computational complexity. 14th Week Intractable problems./Cellular Automata.
RECOMENDED 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 WORKLOAD	Activities Number Hours Workload 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 Workload 313 Total Workload / 30 10,43 ECTS Credits of the Course 10
LANGUAGE OF INSTRUCTION	Turkish
WORK PLACEMENT(S)	No