Knowledge in THEORY OF COMPUTATION

THEORY OF COMPUTATION ( F-SCHEME) : 3RD YEAR ( DRONACHARYA COLLEGE OF ENGINEERING)

A COMPLETE DETAILED STEP BY STEP, HANDWRITTEN NEAT AND CLEAN NOTES OF THEORY OF COMPUTATION, COVERING THE WHOLE SYLLABUS.

unit 3 CFG

it covers all the topics related to context free grammar with very basic examples

unit 4 PDA

It covers all the topics related to unit 4 pushdown automata with a variety of examples as prescribed by AKTU

TURING MACHINE

It covers all the topics of turing machine with a variety of examples as prescribed by AKTU syllabus

CS1013 THEORY OF COMPUTATION

UNIT I - FINITE AUTOMATA (9 hours) Introduction- Basic Mathematical Notation and techniques- Finite State systems –Basic Definitions – Finite Automaton – DFA & NDFA – Finite Automaton with €-moves – Regular Languages- Regular Expression – Equivalence of NFA and DFA – Equivalence of NDFA’s with and without €-moves – Equivalence of finite Automaton and regular expressions –Minimization of DFA- - Pumping Lemma for Regular sets – Problems based on Pumping Lemma.

CS1013 THEORY OF COMPUTATION

UNIT II - GRAMMARS (9 hours) Grammar Introduction– Types of Grammar - Context-Free Grammars and Languages– Derivations and Languages – Ambiguity- Relationship between derivation and derivation trees – Simplification of CFG – Elimination of Useless symbols - Unit productions - Null productions – Greyback Normal form – Chomsky normal form – Problems related to CNF and GNF.

CS1013 THEORY OF COMPUTATION

UNIT III - PUSHDOWN AUTOMATA (9 hours) Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Equivalence of Pushdown automata and CFL - pumping lemma for CFL – problems based on pumping Lemma.

CS1013 THEORY OF COMPUTATION

UNIT IV - TURING MACHINE (9 hours) Turing Machines- Introduction – Formal definition of Turing machines – Instantaneous descriptions- Turing Machine as Acceptors – Turing Machine as Transducers Computable Languages and functions – Turing Machine constructions – Modifications of Turing Machines.

CS1013 THEORY OF COMPUTATION

Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata Theory, Languages and Computations”, Third Edition, Pearson Education, 2008.

CS1013 THEORY OF COMPUTATION

UNIT V - COMPUTATIONAL COMPLEXITY (9 hours) Undecidability- Basic definitions- Decidable and undecidable problems - Properties of Recursive and Recursively enumerable languages – Introduction to Computational Complexity: Definitions-Time and Space complexity of TMs – complexity classes – introduction to NP-Hardness and NP-Completeness

Automata Mathematical Part

Mathematical part of automata

Theory of Computation Manit Bhopal paper- 2nd year

Theory of Computation Manit Bhopal previous year paper