Theory of Computation (TOC) Course Content
Here is TOC Course Content along with Marks Distribution. Practice Well!!
Marks Distribution
| Chapters | Hours | Marks |
|---|---|---|
| 1. Introduction | 4 | 7 |
| 2. Finite Automata | 12 | 21 |
| 3. Context free language | 12 | 21 |
| 4. Turing machine | 10 | 17 |
| 5. Undecidability | 5 | 9 |
| 6. Computational Complexity | 2 | 5 |
| Total | 45 | 80 |
Introduction
- Set, relation, function, Proof techniques
- Alphabets, language, regular expression
Finite Automata
- 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
- 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
- Definition of Turing machine, notation for Turing machine
- Computing with Turing machine
- Extensions of Turing machine
- Unrestricted grammar. (PDF – cs.tau.ac.il)
- Recursive function theory
Undecidability
- The Church‐Turing thesis
- Halting Problem, Universal Turing machine
- Undecidable problems about Turing machines, grammar.
- Properties of Recursive, Recursively enumerable languages.
Computational Complexity
TOC Course Content – Notes IOE