RTMNU TY CSE (DS) syllabus

RTMNU · Third Year B.Tech Computer Science & Engineering (Data Science) · NEP 2020

Theory of Computation

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

  1. Unit 1: Introduction

    7 hours

    Strings, alphabets, languages and their operations; finite state machines and the acceptance of strings and languages; NFA and DFA, their equivalence and conversion; minimisation and equivalence of FSMs; Moore and Mealy machines.

    Examined in the 70-mark end-semester paper

  2. Unit 2: Regular Sets, Regular Expressions

    8 hours

    Regular sets and expressions, identity rules and manipulation of regular expressions; equivalence and inter-conversion of RE and FA; the pumping lemma and closure properties of regular sets; regular, right-linear and left-linear grammars, their equivalence with FA and inter-conversion between RE and RG.

    Examined in the 70-mark end-semester paper

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

    7 hours

    Context-free grammars, derivation trees, Chomsky and Greibach normal forms; pushdown automata, their model and acceptance of CFLs; equivalence and inter-conversion of CFLs and PDAs; properties of CFLs.

    Examined in the 70-mark end-semester paper

    • Derivation trees, sentential forms and ambiguity
    • Chomsky and Greibach normal forms
    • Pushdown automata and acceptance
    • Equivalence of CFG and PDA
    • Closure properties of context-free languages
  4. Unit 4: Turing Machine and Undecidability

    7 hours

    The Turing machine model and design, the universal Turing machine, computable functions, recursively enumerable languages, Church's hypothesis, counter machines and types of TMs; properties of recursive and recursively enumerable languages, Post's correspondence problem and an introduction to recursive function theory.

    Examined in the 70-mark end-semester paper

    • Turing machines and their design
    • Variants of Turing machines and the universal TM
    • Church–Turing thesis
    • Recursive and recursively enumerable languages
    • Decidability and the halting problem
    • Post correspondence problem
    • Primitive recursive and μ-recursive functions

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