Learning 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) :
Finite Automata & Regular Languages
Languages vs Problems. Finite State Automata, Regular Languages. Closure properties, Limitations, Pumping Lemma, MyhillNerode relations, Quotient Construction. Minimization Algorithm.
Nondeterminism & Regular Expressions
Notion of nondeterminism. Acceptance condition. Subset construction. Pattern matching and regular expressions. Regular Expressions and Regular languages. More closure properties of regular languages.
Grammars & Contextfree Languages(CFLs)
Grammars and Chomsky Hierarchy, CFLs, Regular Grammars, Chomsky Normal Form, Pumping Lemma for CFLs, Inherent Ambiguity of ContextFree Languages, CockYoungerKasami Algorithm, Applications to Parsing. Pushdown Automata(PDA), PDA vs CFLs. Deterministic CFLs.
Turing Machines & Computability
Introduction to Turing Machines, Configurations, Halting vs Looping. Multitape Turing machines. Recursive and Recursively enumerable languages. Undecidability of Halting Problem. Reductions. Introduction to Theory of NPcompleteness.
TextBook(s)

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 McGrawHill, 2003.
Meta Data
 Proposing Faculty : IIT Madras course
 Department / Centre : Computer Science and Engineering
 Programme : B.Tech
 Proposal Type: Old
 Offerings
 2017 JanApr Dr. Deepak Rajendraprasad