Theory of Computation Notes
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.
Subject at a glance
4
Units
32
Topics
4
Credits
4
Infographics
Unit-wise Syllabus
4 units — open any unit for detailed topic-wise notes, diagrams and important exam questions
- 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
Transitions per input
Exactly one
Zero, one or many
ε-moves
Not allowed
Allowed (ε-NFA)
Power
Same: regular languages
Same: regular languages
Size
Can be exponentially larger
Often smaller
Study guide
This unit covers formal languages, the diagonal argument, DFA and NFA and their equivalence, Mealy and Moore machines, minimisation, regular languages, grammars and expressions, the pumping lemma and lexical analysis. Practise constructing DFAs for given languages.
- Properties of context-free languages
- Chomsky classification
- context-free grammars
- grammar simplification
- Chomsky Normal Form
- Greibach Normal Form
- Type 0: recursively enumerable
Turing machine
- Type 1: context-sensitive
Linear bounded automaton
- Type 2: context-free
Pushdown automaton
- Type 3: regular
Finite automaton
Study guide
You study properties of context-free languages, the Chomsky classification, context-free grammars, simplification, Chomsky Normal Form and Greibach Normal Form. Practise converting grammars to CNF.
- 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
Rule shapes
A → BC or A → a
A → a followed by variables
Use
CYK parsing algorithm
Top-down parsing, PDA construction
Derivation length
2n − 1 steps for a string of length n
n steps
Study guide
You study ambiguity, parse trees, pushdown automata and equivalence, non-deterministic PDA, Turing machines and variations, universal Turing machines, the Church-Turing thesis, recursive and recursively enumerable languages and the Chomsky hierarchy. Construct Turing machines for simple problems.
- Unsolvable problems
- the halting problem
- Post correspondence problem
- unsolvable problems for context-free languages
- measuring and classifying complexity
- tractable and intractable problems
Decidable
A TM always halts with yes or no
Is a string in a regular language?
Undecidable
No algorithm exists
Halting problem, Post correspondence
P
Solvable in polynomial time
Sorting, shortest path
NP-complete
Hardest problems in NP
SAT, travelling salesman (decision)
Study guide
You study unsolvable problems, the halting problem, Post correspondence problem, undecidability for CFLs, complexity measurement and tractable versus intractable problems. Understand why the halting problem cannot be solved.
Why Theory of Computation Matters
Theory of computation explains what computers can and cannot do, and underlies compiler design, language processing and algorithm theory, as well as GATE and research.
How to Prepare for Theory of Computation
- Practise automata constructions and proofs.
- Learn the Chomsky hierarchy as a table of machines and grammars.
- Understand the intuition behind undecidability.
Theory of Computation: Frequently Asked Questions
What is the halting problem?
It is the problem of deciding whether a given program will stop or run forever, which has been proven impossible to solve in general.