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

The students


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 schedule

TestTimeTotal pointsDuration (Tentative) syllabusQuestion paper
Mid-semester test 1September 4, 2002, 8:00pm onwards 251 hour1,2 [Questions] [Solutions]
Mid-semester test 2October 6, 2002, 4:00pm onwards 251 hour3 [Questions] [Solutions]
End-semester testDecember 4, 2002, 8:00am onwards 503 hours1--5 [Questions] [Solutions]

Text books

Tutorial exercises

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.