Y2HLYes to Happy Learning

Courses / TOC

24CS3206 · Theory · Undergraduate, no prerequisites

Theory of Computation

by Dr. Asesh Kumar Tripathy

Machines, languages and the limits of computation. Finite automata, regular expressions, grammars, pushdown automata and Turing machines, built up one topic at a time. Every topic ends with a self-marking quiz, and your marks are kept on a marks page.

  • 26topics
  • 26quizzes
  • 4CO tests
  • 4course outcomes
Start Topic 1 How to study this course

The 26 topics

CO1Finite automata and regular languages

Topic 1 Deterministic finite automata (DFA) Topic 2 NFA and DFA–NFA equivalence Topic 3 Regular expressions and finite automata Topic 4 Arden's theorem Topic 5 Minimisation of DFA Topic 6 Moore machines Topic 7 Mealy machines and Moore–Mealy conversion CO1 test 20 questions from these topics

CO2Limits of regular languages and context-free grammars

Topic 8 Closure properties and regular grammars Topic 9 Pumping lemma for regular languages Topic 10 Context-free grammars Topic 11 Derivations, parse trees and ambiguity Topic 12 Simplification of CFGs Topic 13 Chomsky and Greibach normal forms CO2 test 20 questions from these topics

CO3Pushdown automata and context-free languages

Topic 14 Pushdown automata Topic 15 PDA acceptance: final state and empty stack Topic 16 CFG–PDA equivalence Topic 17 Pumping lemma for context-free languages Topic 18 Closure properties of context-free languages Topic 19 Context-sensitive grammars Topic 20 Linear bounded automata CO3 test 20 questions from these topics

CO4Turing machines and decidability

Topic 21 Turing machines: model and notation Topic 22 Turing machine construction techniques Topic 23 Turing machines as language acceptors Topic 24 Recursive and recursively enumerable languages Topic 25 Chomsky hierarchy, universal TM and the halting problem Topic 26 Variants of Turing machines: multi-tape and nondeterministic CO4 test 20 questions from these topics

See my marks →

How to study this courseThe topic, quiz and CO test rhythm, how marks are kept, and how to get the most out of the tutorial problems. Tutorial workbookWhere each of the 20 tutorial sessions is covered on this site, so you can find the practice problems for any session.

Course overview

The goal of this course is to decide whether a given problem can be solved by a machine at all, and if it can, to identify the simplest machine that solves it.

Theory of Computation studies the mathematical models behind every computer. You will meet a ladder of machines: finite automata, pushdown automata and Turing machines. Each rung recognises more languages than the one below it. The question running through every topic is the same: what is the weakest machine that can do this job, and how do we prove that a weaker one cannot?

The course has no prerequisites beyond school mathematics: sets, functions and proof by induction. You will not write programs. You will design machines and grammars on paper, and prove things about them.

Course outcomes

CO You will be able to Level
CO1 Apply DFA and NFA concepts to recognise regular languages, show their equivalence with regular expressions using Arden's theorem, and minimise DFAs. Apply
CO2 Analyse context-free languages: use closure properties and the pumping lemma to prove languages non-regular, and derive normal forms of grammars. Analyse
CO3 Analyse how pushdown automata recognise context-free languages, examining the role of the stack and the two ways of accepting. Analyse
CO4 Compare decidable and undecidable languages by building Turing machines and classifying problems in the Chomsky hierarchy. Analyse

Syllabus

Textbooks

Topic pages refer to these books by number.

  1. Textbook 1: Introduction to the Theory of Computation, 3rd edition, Cengage, 2015.
  2. Textbook 2: Introduction to Automata Theory, Languages and Computation, 3rd edition, Pearson, 2008.
  3. Textbook 3: An Introduction to Formal Languages and Automata, 6th edition, Jones and Bartlett, 2016.

Reference books: 1. Introduction to Languages and the Theory of Computation, 3rd edition. 2. Theory of Computer Science: Automata, Languages and Computation, 3rd edition, PHI. Its finite-automata chapter covers Moore and Mealy machines and Arden's theorem. 3. Automata and Computability, Springer.

Free online lectures