RTMNU SY AI & ML syllabus

RTMNU · Second Year B.Tech Artificial Intelligence & Machine Learning · NEP 2020

Theory of Computation

BAM4T14 · Semester IV · 3 credits · College 30 + university 70

  1. Unit 1: Finite Automata and Regular Languages

    8 hours

    DFAs 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

  2. Unit 2: Context-Free Languages and Pushdown Automata

    7 hours

    Context-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
  3. Unit 3: Turing Machines and Decidability

    7 hours

    Turing 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
  4. Unit 4: Computability and Complexity

    7 hours

    Computability 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
  5. Unit 5: Complexity Classes

    7 hours

    The 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).