Showing posts with label Theory of Computation. Show all posts
Showing posts with label Theory of Computation. Show all posts

Monday, September 15, 2008

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