Computer Science & Engineering needs a mathematical language to abstract away from particulars of computing machinery and to concentrate on systematicity, capacity, and efficiency of computing in the abstract. Theory of Formal Languages is one such language (Complexity Theory is another). The theory has found scientific and practical use in CS theory, programming languages, compilers, concurrent processes, AI, etc. In fact, description of any computational process can be recast in formal language theory. From this perspective, the theory can be seen as a vehicle for communicating the ideas clearly and precisely among computer scientists. This course is an introduction to the topic.
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 verbally specified CFLs.
- 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