Theory of Computation
Course Objectives:
To provide basic understanding of theory of automata, formal languages, turing machines and computational complexity.
- Introduction (4 hours)
- Set, relation, function, Proof techniques.
- Alphabets, language, regular expression.
- Finite Automata (12 hours)
- Deterministic Finite Automata.
- Non-Deterministic Finite Automata.
- Equivalence of regular language and finite automata.
- Regular language, properties of regular language.
- Pumping lemma for regular language.
- Decision algorithms for regular languages.
- Context free language (12 hours)
- Context free grammar.
- Derivative trees, simplification of context free grammar.
- Chomsky normal form.
- Push down automata.
- Equivalence of context free language and push down automata.
- Pumping lemma for context free language.
- Properties of context free language.
- Decision algorithms for context free language.
- Turing machine (10 hours)
- Definition of Turing machine, notation for Turing machine.
- Computing with Turing machine.
- Extensions of Turing machine.
- Unrestricted grammar.
- Recursive function theory.
- Undecidability (5 hours)
- The Church-Turing thesis.
- Halting Problem, Universal Turing machine.
- Undecidable problems about Turing machines, grammars.
- Properties of Recursive, Recursively enumerable languages.
- Computational Complexity (2 hours)
- Class P, Class NP, NP-complete problems.
References
- H. R. Lewis, C. H. Papadimitriou, “Elements of theory of computation”, Pearson Education.
- Michael Sipser, “Introduction to the Theory of Computation”, Thomson Course Technology.
Evaluation Scheme
The questions will cover all the chapters of syllabus. The evaluation scheme will be as indicated in the table below:
|
Chapters |
Hours |
Marks Distribution* |
1 |
4 |
7 |
2 |
12 |
21 |
3 |
12 |
21 |
4 |
10 |
17 |
5 |
5 |
9 |
6 |
2 |
5 |
Total |
45 |
80 |
*Note: There could be a minor deviation in the marks distribution.
|
