About Theory of Computation (PCCST302)
Theory of Computation (PCCST302) is a third-semester course in the KTU B.Tech 2024 scheme, common to CSE and its allied branches. It studies what computers can and cannot do, using simple mathematical models of computation such as finite automata, pushdown automata and Turing machines. These ideas sit behind compilers, text search, programming language design and the limits of algorithms.
Syllabus
- Module 1: Alphabets, strings and languages, deterministic and non-deterministic finite automata (DFA and NFA), NFA to DFA conversion, and DFA minimization.
- Module 2: Regular expressions and regular grammars, properties of regular languages and the pumping lemma, and context-free grammars, parse trees and ambiguity.
- Module 3: Pushdown automata, simplifying grammars into Chomsky and Greibach normal forms, and properties of context-free languages.
- Module 4: Turing machines, the Chomsky hierarchy, the Church-Turing thesis, and undecidable problems such as the halting problem and Post's correspondence problem.
Exam pattern
The end-semester exam is for 60 marks: 8 short questions of 3 marks each, plus 4 questions of 9 marks each, one from each module. Internal assessment adds 40 marks.
Study tips
Practise designing automata and grammars for many example languages, since design questions carry the most marks. Learn the standard conversions step by step (NFA to DFA, regular expression to automaton, grammar to normal form), and solve previous question papers to spot repeated problem types.
Notes and resources
Find module-wise notes, solved problems, previous year question papers and the syllabus for PCCST302 here, shared by KTU students and teachers.