Credits: 3 (3-0-0)
Prerequisites: MTL342
Overlaps with: COL352
Description
Introduction to the Theory of Computation: Proof Techniques, Basic concepts of language, Grammar and Automata; Chomsky Hierarchy, Regular Languages, Finite automata, Equivalence, DFA and NFA, Minimization, Myhill-Nerode Theorem; Context Free Grammar, Pushdown Automata their equivalenece and Application, Properties of Context-Free Languages; Turing Machine, Recursive and Recursively Enumerable Languages; Undecidability, Rice’s Theorem, Post’s Correspondence Problem, Complexity Theory, Intractable Problems.
Prerequisite Tree
flowchart TD
MTL783-622[MTL783]
MTL783-622 --> MTL342-622[MTL342]
MTL342-622 --> MTL180-622[MTL180]
classDef empty height:17px, fill:transparent, stroke:transparent;
classDef trueEmpty height:0px, width:0px;