MG University S7 computer Science and Engineering B.Tech Syllabus
Module 1
Introduction to the theory of computation – Set theory – Definition of sets – Properties – Countability – Uncountability – Equinumerous sets – Functions – Primitive recursive and partial recursive functions – Computable and non computable functions – Diagonalization principle – Formal representation of languages – Chomsky Classification.
Introduction to the theory of computation – Set theory – Definition of sets – Properties – Countability – Uncountability – Equinumerous sets – Functions – Primitive recursive and partial recursive functions – Computable and non computable functions – Diagonalization principle – Formal representation of languages – Chomsky Classification.
Module 2
Introduction to Automata theory – Definition of Automation – Finite Automata – Formal definition – Language acceptability by Finite Automata – Transition Diagrams and Transition systems – Deterministic and Nondeterministic finite automation – Finite Automation with -Transitions – Eliminating -Transitions – Conversion of NFA to DFA – Regular operations – Regular Expressions – Pumping lemma for regular languages – Applications of finite state automata – Lexical analysers – Text search.
Introduction to Automata theory – Definition of Automation – Finite Automata – Formal definition – Language acceptability by Finite Automata – Transition Diagrams and Transition systems – Deterministic and Nondeterministic finite automation – Finite Automation with -Transitions – Eliminating -Transitions – Conversion of NFA to DFA – Regular operations – Regular Expressions – Pumping lemma for regular languages – Applications of finite state automata – Lexical analysers – Text search.
Module 3
Pushdown Automata – Formal definition – Language acceptability by PDA – Deterministic and nondeterministic PDA – Context free grammar – Applications of PDA – Parsing.
Pushdown Automata – Formal definition – Language acceptability by PDA – Deterministic and nondeterministic PDA – Context free grammar – Applications of PDA – Parsing.
Module 4
Turing Machines – Formal definition – Language acceptability – Universal Turing Machines – Halting Problem of Turing Machines – Church’s Thesis – Godelization.
Turing Machines – Formal definition – Language acceptability – Universal Turing Machines – Halting Problem of Turing Machines – Church’s Thesis – Godelization.
Module 5
Algorithmic complexity – Tractable and intractable problems – Complexity classes – Class P – Class NP – NP Complete and NP Hard problems.
Algorithmic complexity – Tractable and intractable problems – Complexity classes – Class P – Class NP – NP Complete and NP Hard problems.
References
1. Introduction to the Theory of Computation- Michael Sipser, Brooks/Cole (Thomson Learning)
2. Theory of Computer Science – K.L.P. Mishra, N. Chandrashekharan, Prentice Hall of India
3. Elements of the theory of computation -Harry R Lewis, Christos H Papadimitriou Prentice Hall of India / Pearson Education Asia
4. The Theory of Computation – Bernard M Morct (Pearson Edn)
5. Introduction to Automata Theory, Languages & Computation John Hopcroft, Rajeev Motwani & Jeffry Ullman (Pearson Edn)
2. Theory of Computer Science – K.L.P. Mishra, N. Chandrashekharan, Prentice Hall of India
3. Elements of the theory of computation -Harry R Lewis, Christos H Papadimitriou Prentice Hall of India / Pearson Education Asia
4. The Theory of Computation – Bernard M Morct (Pearson Edn)
5. Introduction to Automata Theory, Languages & Computation John Hopcroft, Rajeev Motwani & Jeffry Ullman (Pearson Edn)