COL352: Difference between revisions
| [checked revision] | [checked revision] |
Prashantt492 (talk | contribs) Creating course page via bot |
Bot: wrap bare course codes in wikilinks |
||
| Line 4: | Line 4: | ||
| credits = 3 | | credits = 3 | ||
| credit_structure = 3-0-0 | | credit_structure = 3-0-0 | ||
| pre_requisites = COL202 | | pre_requisites = [[COL202]] | ||
| overlaps = | | overlaps = | ||
}} | }} | ||
Latest revision as of 16:26, 14 April 2026
| COL352 | |
|---|---|
| Introduction to Automata & Theory of | |
| Credits | 3 |
| Structure | 3-0-0 |
| Pre-requisites | COL202 |
| Overlaps | |
COL352 : Introduction to Automata & Theory of
Regular Languages, Finite Automata, equivalence, minimization, Myhill-Nerode Theorem, introduction to non-determinism, Context free grammars, Pushdown automata, equivalence and applications. Turing machines, Recursive and Recursively enumerable sets, non-determinism, RAMs and equivalence, Universal Turing Machines, undecidability, Rice's theorems for RE sets, Post machines, Basics of Recursive function theory. Equivalence, Church's thesis, computational complexity, space and time complexity of Turing Machines, Relationships, Savage's theorem, Complexity classes, Complete problems, NP-completeness, Cook-Levin theorem.