At the end of this course, students will be able to:

Define languages formally using mathematical abstraction methods. Formalize recognizers and acceptors for languages. Identify regular languages, context free languages, recursively enumerable languages and the automata accepting these Convert NFAs to their corresponding DFAs Create regular expressions for regular langauges Design a NFA for a given regular language/regular expression Implement minimization for DFAs Design grammars for context free languages Create PDAs for a given CFL Create PDA for a given CFG Recognize and design deterministic PDAs Recognize non-context free languages Prove  a language non-context free using pumping lemma Convert CFGs to normal forms Construct a PDA from a given CFG Simulate top-down and bottom-up parsing approaches Design and  create Turing machines for recursive languages Distinguish recursively enumerable  and recursive languages Design Turing machines for function computations Simulate the behaviour of a particular variation of a Turing machine by a standard Turing machine and vice versa Prove equivalence of variations of Turing machines Identify and build universal Turing machines Identify non-deterministic Turing machines Understand the limits of computation (Halting problem) Understand the formal definition of an algorithm (Church Turing thesis) Classify computational problems into different classes according to the computational power they require