Course Objectives
Course should provide a formal connection between algorithmic problem solving and the theory of languages and automata and develop them into a mathematical (and less magical) view towards algorithmic design and in general computation itself. The course should in addition clarify the practical view towards the applications of these ideas in the engineering part of CS.
Syllabus
Four basic themes (but related in a flow) : 44L + 12T
- Finite Automata & Regular Languages - 13L + 3T
Languages vs Problems. Finite State Automata, Regular Languages.
Closure properties, Limitations, Pumping Lemma, Myhill-Nerode relations, Quotient Construction. Minimization Algorithm.
-
Non-determinism & Regular Expressions - 8L + 2T
Notion of non-determinism. Acceptance condition. Subset construction. Pattern matching and regular expressions. Regular Expressions and Regular languages. More closure properties of regular languages.
-
Grammars & Context-free Languages(CFLs) - 15L + 5T
Grammars and Chomsky Hierarchy, CFLs, Regular Grammars, Chomsky Normal Form, Pumping Lemma for CFLs, Inherent Ambiguity of Context-Free Languages, Cock-Younger-Kasami Algorithm, Applications to Parsing. Pushdown Automata(PDA), PDA vs CFLs. Deterministic CFLs.
-
Turing Machines & Computability - 9L + 2T
Introduction to Turing Machines, Configurations, Halting vs Looping. Multi-tape Turing machines. Recursive and Recursively enumerable languages. Undecidability of Halting Problem. Reductions. Introduction to Theory of NP-completeness.
Textbooks
- Automata and Computability, Dexter C. Kozen, Springer Publishers, 2007.
- Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani, and Ullman, Pearson Publishers, Third Edition, 2006.
References:
- Elements of the Theory of Computation, H. R. Lewis and C.H. Papadimitriou, Prentice Hall Publishers, 1981
- Introduction to Languages and the Theory of Computation, John. C. Martin, Tata McGraw-Hill, 2003.
Learning Outcomes:
After completing the course, the student will be able to:
-
Model, compare and analyse different computational models using combinatorial methods.
-
Apply rigorously formal mathematical methods to prove properties of languages, grammars and automata.
-
Construct algorithms for different problems and argue formally about correctness on different restricted machine models of computation.
-
Identify limitations of some computational models and possible methods of proving them.
-
Have an overview of how the theoretical study in this course is applicable to and engineering application like designing the compilers.
