Theory of Computation (IT-5001)

Syllabus



UNIT 1: Introduction of the theory of computation Introduction of the theory of computation, Finite state automata – description of finite automata, properties of transition functions, Transition graph, designing finite automata, FSM, DFA, NFA, 2-way finite automata, equivalence of NFA and DFA, Mealy and Moore machines.
UNIT 2: Regular grammars Regular grammars, regular expressions, regular sets, closure properties of regular grammars, Arden’s theorem, Myhill-Nerode theorem, pumping lemma for regular languages, Application of pumping lemma, applications of finite automata, minimization of FSA.
UNIT 3: Introduction of Context-Free Grammar Introduction of Context-Free Grammar - derivation trees, ambiguity, simplification of CFGs, normal forms of CFGs- Chomsky Normal Form and Greibach Normal forms, pumping lemma for CFLs, decision algorithms for CFGs, designing CFGs, Closure properties of CFL’s.
UNIT 4: Introduction of PDA Introduction of PDA, formal definition, closure property of PDA, examples of PDA, Deterministic Pushdown Automata, NPDA, conversion PDA to CFG, conversion CFG to PDA.
UNIT 5: Turing machines Turing machines - basics and formal definition, language acceptability by TM, examples of TM, variants of TMs – multitape TM, NDTM, Universal Turing Machine, offline TMs, equivalence of single tape and multitape TMs. Recursive and recursively enumerable languages, decidable and undecidable problems – examples, halting problem, reducibility. Introduction of P, NP, NP complete, NP hard problems and Examples of these problems.


CDGI

  1. UNIT 1,2 (By Vivek Kumar Gupta Sir)

You may also like

CDGI - 3rd Year - Computer Graphics & multimedia - (CGMM)

CDGI - 3rd Year - Computer Graphics & multimedia - (CGMM)

IIST - 3rd Year - Operating System (OS)