Theory of Computation

Course Objective
To provide an idea of the theory of formal languages, automata and complexity theory.

1.0 Finite automata and regular expression: ( 5 hours)
1.1 Finite state system
1.2 Non-deterministic finite automata
1.3 Regular expression

2.0 Properties of regular sets: ( 4 hours)
2.1 The plumbing lemma for regular sets
2.2 Closure properties of regular sets
2.3 Decision algorithms for regular sets

3.0 Context-free grammers: ( 8 hours)
3.1 Derivative trees
3.2 Simplification of context-free grammars
3.3 Normal forms

4.0 Pushdown automata: ( 4 hours)
4.1 Pushdown automata and context-free grammars

5.0 Properties of context-free languages: ( 6 hours )
5.1 The pumping lemma for CFL's
5.2 Closure properties of CFL's
5.3 Decision algorithms for CFL's

6.0 Turing Machines: (5 hours)
6.1 Computable languages and functions
6.2 Church's hypothesis

7. Undecidability (5 hours )
7.1 Properties of recursive and recursively languages
7.2 Universal turing machines and undecidable problem
7.3 Recursive function theory

8. Computational complexity theory: ( 4 hours)

9. Intractable problems: ( 4 hours)
9.1 Computable languages and functions
9.2 NP-complete problems

References:
1. H.R. Lewis, and C.H. Papadimitriou, " Element of the theory of Computation". Eastern Economy Edition, Prentice Hall of India
2. R. McNaughton, " Elementary Computability, Formal languages and Automata", Prentice Hall of India
3. E. Engeler, " Introduction to the Theory of Computation", Academic Press