Theory of Computation
Subject Overview
The first Elective-I option, covering formal language theory — finite automata and regular languages, context-free grammars and normal forms, pushdown automata, and Turing machines, computability and computational complexity including the halting problem. A 4-credit elective theory paper.
Unit-wise Syllabus
4 units — click WhatsApp below to get the full notes for each
Unit 1: Automata and regular languages
Formal language, diagonal argument, deterministic and non-deterministic finite automata and their equivalence, Mealy and Moore models, finite automata minimization, regular languages/grammars/expressions, pumping lemma, non-regular languages, lexical analysis
Unit 2: Context-free languages
Properties of context-free languages, Chomsky classification, context-free grammars, grammar simplification, Chomsky Normal Form, Greibach Normal Form
Unit 3: Pushdown automata and Turing machines
Ambiguity, parse trees, equivalence of PDAs, non-deterministic PDA, standard Turing machines and variations, universal Turing machines, Church-Turing thesis, recursive and recursively enumerable languages, context-sensitive languages, Chomsky hierarchy, TM construction for simple problems
Unit 4: Unsolvability and complexity
Unsolvable problems, the halting problem, Post correspondence problem, unsolvable problems for context-free languages, measuring and classifying complexity, tractable and intractable problems