E0 222 Formal Methods in Computer Science
The course will essentially be a course on
Theory of Computation
Finite automata and their use in modelling,
context free languages,
Books and other material
Hopcroft J.E. and Ullman, J.D.: Introduction to Automata, Languages and Computation. Addison Wesley, 1979.
Dexter Kozen: Automata and Computability. Springer, 1999.
H. R. Lewis and C. H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1981.
C. H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
Dexter Kozen: On regularity preserving functions
Seminar Topics (meetings on Mondays 5pm).
Kleene Algebras and Regular Expressions
(Anand S. and Tarun Ramsinghani) 28 August 2005.
Collapsing Non-deterministic automata
(Ashutosh and Nitin) 12 September.
Matrix approach to regularity preserving functions
(Prashant and Arun) 10th October.
(Mathew Francis and Rogers Mathew) 17th October.
: (Vamsi Krishna and Koteswara Rao)
CKY parsing algorithm
(Amareshwari and Laxmi) Mon 7th November.
The Chomsky-Schutzenberger theorem (
)(Rathijit Sen and ?) Fri 11th November
Mu-recursive functions capture Turing computable functions
(Prachee Jindal and Megha Mahobey) Mon 14th Nov
Context Sensitive Grammars and Linear Bounded Automata
(Babaria Rashmin and Mehul Parsana) Mon 21th Nov.
Undecidability of Post Correspondence Problem and Tiling Problem (Rupesh Bajaj, Sandeep Tandekar, Sudipta Chattopadhyay) Friday 25th Nov.
(Rajeev Verma, Sanjay Waghela) Mon 28th Nov.
Logical characterisation of regular languages
Grammars and computability
Weightage for evaluation:
Mid-semester Exam: 20%
Assignments (Lab + written) + Seminar: 40%
Final Exam: 40%
Current meeting schedule: Tue & Thu 3:30 pm, in CSA Seminar Room.
Thu 29th September, 3:30--5:00pm
2:00pm, Mon 12th December 2005