RTMNU SY AI & DS syllabus

RTMNU · Second Year B.Tech Artificial Intelligence & Data Science · NEP 2020

Theory of Computation

BAD4T13 · Semester IV · 4 credits · College 30 + university 70

A 4-credit course with a weekly tutorial.

  1. Unit 1: Finite Automata

    8 hours

    Alphabets, sets and languages and the Chomsky hierarchy; DFAs, their transition diagrams and tables and languages; NFAs and their equivalence with DFAs; ε-transitions and their elimination; DFA minimisation; Moore and Mealy machines and their interconversion.

    Examined in the 70-mark end-semester paper

  2. Unit 2: Regular Expressions and Regular Grammars

    7 hours

    Identities of regular expressions; converting DFAs to regular expressions and regular expressions to automata; regular, right-linear and left-linear grammars and their finite automata; the pumping lemma and closure properties of regular languages.

    Examined in the 70-mark end-semester paper

    • Regular expressions and identities
    • Arden's theorem: FA to RE
    • Converting RE to FA
    • Regular grammars and finite automata
    • Pumping lemma for regular languages
    • Closure properties of regular languages
  3. Unit 3: Context-Free Grammars

    7 hours

    Derivation trees and sentential forms, Chomsky and Greibach normal forms, ambiguity, minimisation of CFGs and the pumping lemma for context-free languages.

    Examined in the 70-mark end-semester paper

  4. Unit 4: Pushdown Automata

    7 hours

    The PDA model, acceptance of context-free languages by final state and by empty stack and their equivalence, and the equivalence of CFGs and PDAs.

    Examined in the 70-mark end-semester paper

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

    7 hours

    The Turing machine model and design, the universal Turing machine, computable functions, linear bounded automata and context-sensitive languages, recursive and recursively enumerable languages, the halting problem, the Post correspondence problem and Church's hypothesis.

    Examined in the 70-mark end-semester paper

    • Turing machines and their design
    • Variants of Turing machines and the universal TM
    • Linear bounded automata and context-sensitive languages
    • Recursive and recursively enumerable languages
    • Decidability and the halting problem
    • Post correspondence problem
    • Church–Turing thesis

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