THEORY OF COMPUTATION

Catalog description

The course is intended to introduce the students to the theory of computation in a fashion that emphasizes breadth and away from detailed analysis found in a normal undergraduate automata course. The topics covered in the course include methods of proofs, finite automata, non-determinism, regular expressions, context-free grammars, pushdown automata, no-context free languages, Church-Turing Thesis, decidability, reducibility, and space and time complexity.