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.
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.