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
