MTH 222 Theory of Computation, Semester I, 2002-2003

MTH 222 Theory of Computation, 3-1-0-4, Semester I, 2002-2003

For enquiries and/or doubts contact me by e-mail or meet me in my office (Faculty building, Room No 567).

1. Languages: Languages and their finite representations, regular expressions.
2. Finite automata: Deterministic and nondetermisnistic finite automata, regular expressions.
3. Pushdown automata: Context-free grammars and languages, parse trees, ambiguity, pushdown automata.
4. Turing machines and Turing computability: Basic Turing machine model, Turing computability, variants of Turing machines, grammars.
5. Undecidability: Church-Turing thesis, universal Turing machines, halting problem, some undecidable problems.
6. Complexity theory (Not covered thoroughly): Complexity classes P, NP and NP-complete, some NP-complete problems.

Test	Time	Total points	Duration	(Tentative) syllabus	Question paper
Mid-semester test 1	September 4, 2002, 8:00pm onwards	25	1 hour	1,2	[Questions] [Solutions]
Mid-semester test 2	October 6, 2002, 4:00pm onwards	25	1 hour	3	[Questions] [Solutions]
End-semester test	December 4, 2002, 8:00am onwards	50	3 hours	1--5	[Questions] [Solutions]

J E Hopcroft, R Motwani and J D Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, second edition, 2000. Low-cost Asian reprints (around 300 Rs) are available from Pearson Education, Singapore. Go for the second edition.
L R Lewis and C H Papadimitriou, Elements of the theory of computation, Prentice-Hall, second edition, 1998. Low-cost Asian reprints (around 250 Rs) are available from Pearson Education, Singapore. Go for the second edition.

0. Preliminaries
1. Languages and regular expressions
2. Finite automata
3. Finite automata and regular expressions
4. Context-free languages
5. Pushdown automata
6. Turing machines
7. Undecidability

Note that the solutions of the tutorial exercises will not be made available electronically. These are practice exercises. Students are expected to try solving them and discuss during the tutorial sessions. Readymade solutions defeat this basic purpose.