Sub : Theory of Computation
Code : EG 632 CT
Sem : III/I
Theory : 20
Assmnt : 80
------------
Total : 100
Syllabus:
1. Finite automata and regular expression
-Finite state system
-Non deterministic finite automata
-Regular expression
2. Properties of regular sets
-The plumbing lemma for regular sets
-Closure properties of regular sets
-Decision algorithm for regular sets
3. Context free grammers
-Derivatice trees
- Simplification of context free grammars
-Normal forms
4. Pushdown automata
-Pushdown automata and contexzt free grammars
5. Properies of context free language
- The pumping lemma for CFL
- Closure properties of CFL's
- Decision algorithm for CFL
6. Turing Machines
-Computable language and functions
-Church hypothesis
7. Undecidability
- Properties of recursive and recursively language
- universal turing machine and undecidable problem
- recursive function theory
8. Computational complexity theory
9. Intractable complexity theory
-Computable language and functions
-NP complete problems
Books:
------
- HR Lewis and CH Papadimitriou " Element of the theory of computation"
- R McNaughton,"Elementary Computability, Formal language and automata"
-E Engeler," Introduction to the theory of computation"
Syllabus Typed By:
-------------------
Mr. Samir Thapa
http://samirthapa.com.np
samirthapa@engineer.com
0 comments:
Post a Comment