RTMNU TY AI syllabus

RTMNU · Third Year B.Tech Artificial Intelligence · NEP 2020

Theory of Computation

BAI6T21 · Semester VI · 3 credits · College 30 + university 70

Only Unit 2 prints its hours.

  1. Unit 1: Finite Automata and Regular Expressions

    Alphabets, strings and languages; deterministic and non-deterministic finite automata and their equivalence; regular expressions, conversion between regular expressions and finite automata, and applications of regular languages.

    Examined in the 70-mark end-semester paper

    • Alphabets, strings and languages
    • Deterministic finite automata
    • NFA and ε-NFA
    • Equivalence of NFA and DFA
    • Regular expressions and identities
    • Converting RE to FA
  2. Unit 2: Properties of Regular Languages

    8 hours

    The pumping lemma for regular languages, closure properties, minimisation of DFA and the Myhill–Nerode theorem (basic idea).

    Examined in the 70-mark end-semester paper

  3. Unit 3: Context-Free Grammars

    Context-free grammars, derivations and parse trees, ambiguity, simplification of CFGs, and the Chomsky and Greibach normal forms.

    Examined in the 70-mark end-semester paper

  4. Unit 4: Pushdown Automata

    Definition and working of PDAs, their types, equivalence of PDAs and CFGs, acceptance by final state and empty stack, and applications of PDAs.

    Examined in the 70-mark end-semester paper

    • Pushdown automata and acceptance
    • Equivalence of CFG and PDA
  5. Unit 5: Turing Machines, Decidability and Complexity

    The Turing machine model, designing Turing machines, their variants, the Church–Turing thesis, decidability and undecidability, and an introduction to complexity (P and NP, basic idea).

    Examined in the 70-mark end-semester paper

Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).