E0 222 Formal Methods in Computer Science

Topics covered

• Finite automata
• Deterministic automata
• Non-deterministic automata
• Operations on languages
• Regular expressions
• Conversion between FA and RE
• Homomorphisms
• Pumping lemma for regular languages
• Ultimate periodicity of regular languages
• DFA minimization
• Myhill-Nerode theorem
• Regularity preserving functions
• Context-free grammars
• Introduction
• Chomsky normal form
• Pumping lemma for CFLs
• Push Down Automata
• Acceptance by final state and empty stack
• Deterministic PDA
• Equivalence of CFGs and PDAs
• Parikh's theorem
• Turing machine and Decidability
• Turing machine
• Enumeration TM
• Closure properities of recursive & r.e. langs
• Universal turing machine
• Halting problem and Membership problem
• Decidability, Reductions
• Rice's theorem
• Godel's incompleteness theorem
• Visibly Pushdown Languages

Texts and references

• Dexter Kozen, Automata and Computability. Springer [book]
• Dexter Kozen, On Regularity-Preserving Functions
• J.I. Seiferas, R. McNaughton, Regularity preserving relations
• Rajeev Alur, P. Madhusudan, Visibly Pushdown Languages

Assignments

• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4
• Assignment 5

Exams

• Mid-Semester Exam
• Final Exam

Seminars

• Kleene's Algebra & Regular Expression (Tarun, Anand)
• Collapsing Nondeterministic Automata (Ashutosh Bhatia, Nitin Rai)
• Matrix Approach to Automata Theory (Prashanth, Arun)
• Two-way Finite Automata (Vamsi Krishna, Koteswara Rao)
• CKY Algorithms (Laxmi, Amareshwari)
• The Chomsky-Schutzenberger theorem (Rathijit Sen, Sriraghavendra)
• Context Sensitive Grammar & Linear Bounded Automata (Mehul, Rashmin)
• Equivalence of mu-Recursive functions and Turing Computable functions (Megha, Prachee)
• Undecidability of PCP and Tiling Problem (Rupesh, Sandeep T, Sudipta)
• Automata on Terms (Rajiv Verma, Sanjay Vaghela)