MCA-118
Theory of Computations
What a machine can compute and at what cost — finite automata and regular languages, grammars and pushdown automata, Turing machines, and complexity classes.
- Semester
- Semester 2
- Credits
- 4
- Scheme
- 3 lectures + 1 tutorial a week
- Contact hours
- 44 across four units
- Category
- Core Elective - I
What the paper is
Theory of Computations is the most abstract paper in the degree and the most durable. It builds a ladder of machines, each strictly more powerful than the last — finite automata, pushdown automata, Turing machines — and for each rung asks two questions: what can it recognise, and what can it provably not?
The method is as examinable as the content. Closure properties and the pumping lemma appear at two levels, for regular and for context-free languages, and both are used the same way: to prove that a particular language is not in a class. That proof pattern is worth learning once and applying twice.
Unit I carries fourteen hours, more than any other unit in the semester, and it includes JFLAP — the tool for constructing DFAs and NFAs. That is unusual for a theory paper and it makes the early material much easier to check yourself on.
What to concentrate on
- DFA and NFA construction, the subset construction for equivalence, and minimisation are the reliable Unit I questions, and they are all mechanical. Practise them until they are quick, because they are also the easiest marks in the paper.
- The pumping lemma is where grades separate. Learn the argument as a game — the adversary picks the pumping length, you pick the string, the adversary decomposes it, you pick the exponent — and the proofs stop feeling like guesswork.
- For Unit IV, you mainly need to state things precisely: what P, NP and PSPACE are, what a polynomial verifier is, and what Savitch's theorem says. It is only eight hours and the questions are correspondingly contained.
Syllabus, unit by unit
Summarised from the approved scheme. Hours are the contact hours the scheme allots, which is a fair guide to where the marks sit.
Unit I · Automata and regular languages
14 hours- Overview and applications of theoretical computer science; alphabets, strings and languages; formal languages
- Finite state machines; deterministic and non-deterministic finite automata, epsilon-closure
- Regular languages, equivalence of DFAs and NFAs, minimisation of finite automata, Mealy and Moore machines
- Regular expressions and their identities, Kleene's theorem, equivalence with DFAs, Arden's theorem
- Closure properties of regular languages, the pumping lemma, non-regular languages
- Introduction to JFLAP and constructing DFAs and NFAs with it
Unit II · Context-free languages and pushdown automata
12 hours- Grammar and context-free grammar, leftmost and rightmost derivation, derivation trees
- Ambiguity and its removal, simplification of grammar
- Normal forms: Chomsky normal form and Greibach normal form
- Context-free languages, deterministic and non-deterministic pushdown automata, equivalence of CFGs and PDAs
- Closure properties of CFLs, the pumping lemma for CFLs, non-context-free languages
Unit III · Turing machines and computability
10 hours- Definition of a Turing machine; recursive and recursively enumerable languages and their closure properties
- Extensions: multi-tape, multidimensional tape and non-deterministic Turing machines, the universal Turing machine
- Equivalence of Turing machine formalisms, the Church-Turing thesis
- Decidability, the halting problem, the Post correspondence problem and its modified form, reducibility
- Chomsky classification
Unit IV · Complexity theory
8 hours- Time and space measures, time complexity, DTIME and NTIME
- Polynomial verifiers and complexity classes, P and NP
- Space complexity, PSPACE, Savitch's theorem
- L and NL, probabilistic computation
How it is examined
- Question 1 is compulsory, covers the whole syllabus, and is made of objective or short-answer questions. It carries 12 marks.
- The rest of the paper is four units matching the four above. Each unit sets two questions and you attempt one, so there are four more answers at 12 marks each.
- Examiners are asked to map every question to a course outcome using Bloom's taxonomy, which is why questions are phrased as “apply”, “analyse” or “evaluate” rather than only “explain”.
The pass mark is 40 out of 100 in every paper.
Learning objectives
- Expressing problems as testing membership in a language
- Designing a mathematical model of computation capable of deciding or recognising a language
- Distinguishing the relative capabilities of different models of computation
- Understanding what is decidable and what is not
- Classifying languages by the space and time complexity of the model
Assumed beforehand
- Discrete Structures
- Knowledge of writing formal mathematical proofs
Paired in the scheme with MCA-168 Lab based on Core Elective I.
Books it is taught from
- TB1Peter Linz, “Introduction to Formal Languages and Automata”, Narosa, 6th edition, 2016
- TB2Michael Sipser, “Introduction to the Theory of Computation”, Cengage Learning, 3rd edition, 2016
- TB3Hopcroft, Motwani and Ullman, “Introduction to Automata Theory, Languages and Computation”, Pearson Education, 3rd edition, 2015
Notes for MCA-118
Lecture notes, question papers and assignments filed against MCA-118 are in the library. Everything there has been checked by a moderator before it appears, and an account is free — new ones are approved by hand, which is what keeps the shelf clean.