RTMNU · Second Year B.Tech Artificial Intelligence & Machine Learning · NEP 2020
Theory of Computation
BAM4T14 · Semester IV · 3 credits · College 30 + university 70
Unit 1: Finite Automata and Regular Languages
8 hoursDFAs and NFAs and their equivalence, regular expressions, properties of regular languages, DFA minimisation and the pumping lemma for regular languages.
Examined in the 70-mark end-semester paper
- Deterministic finite automata
- NFA and ε-NFA
- Equivalence of NFA and DFA
- Minimisation of DFA
- Regular expressions and identities
- Closure properties of regular languages
- Pumping lemma for regular languages
Unit 2: Context-Free Languages and Pushdown Automata
7 hoursContext-free grammars, Chomsky and Greibach normal forms, pushdown automata, parsing techniques, properties and closure properties of context-free languages, the pumping lemma for CFLs and applications in compiler design.
Examined in the 70-mark end-semester paper
- Derivation trees, sentential forms and ambiguity
- Chomsky and Greibach normal forms
- Pushdown automata and acceptance
- Closure properties of context-free languages
- Pumping lemma for context-free languages
- Role of the parser
Unit 3: Turing Machines and Decidability
7 hoursTuring machines and their variants, the Church–Turing thesis, decidability and undecidability, the universal Turing machine, the halting problem, and recursive and recursively enumerable languages.
Examined in the 70-mark end-semester paper
- Turing machines and their design
- Variants of Turing machines and the universal TM
- Church–Turing thesis
- Decidability and the halting problem
- Recursive and recursively enumerable languages
Unit 4: Computability and Complexity
7 hoursComputability theory, reducibility, Rice's theorem and the Post correspondence problem; an introduction to complexity theory with time and space complexity measures.
Examined in the 70-mark end-semester paper
- Reducibility and Rice's theorem
- Post correspondence problem
- Complexity measures for Turing machines
Unit 5: Complexity Classes
7 hoursThe classes P, NP, NP-complete and NP-hard, approximation algorithms, space complexity with PSPACE, L and NL, Cook's theorem and applications of complexity theory.
Examined in the 70-mark end-semester paper
- P, NP and NP-complete problems
- Cook's theorem and polynomial-time reduction
- Approximation algorithms
- Space complexity classes: PSPACE, L and NL
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).