**CDS 303****: Theory of Computation **

*Course Contents*:

*Module-1*:

Introduction, definition, concept of sequential circuits, state table & state assignments, concept of synchronous, asynchronous and linear sequential machines. Basic definition, mathematical representation, Moore versus Mealy m/c, capability & limitations of FSM, state equivalence & minimization, machine equivalence, incompletely specified machines, merger graph & compatibility graph, merger table, Finite memory, definite, information loss less & inverse machines: testing table & testing graph.

*Module-2*:

FSA, NFSA, NFSA with € moves, Regular expressions, Equivalence of regular expression and FSA, Equivalence of type 3 grammars and FSA, Pumping lemma, Closure and decidability results, Myhill-Nerode theorem, Minimization.

*Module-3*:

Grammars, Languages generated, Chomsky Hierarchy, CFG, Ambiguity, Reduced grammars, Normal forms. Pumping lemma & its application, closure properties. Context Free Grammars: Introduction, definition, derivation trees, simplification, CNF & GNF.

*Module-4*:

Pushdown Automata, Acceptance by final state and empty stack, Equivalence to CFG, Deterministic PDA.

*Module-5*:

Turing Machines - Construction, Techniques of TM construction, TM as acceptor and i/o device, Problems. Generalized and restricted versions.

*Module-6*:

Halting problems - Universal TM-recursive and recursively enumerable sets - Decidability - Rice’s Theorem, PCP.

*Text Books*:

Previous | Back to Course List | Next |