RTMNU SY CSE (DS) syllabus

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

Theory of Computation

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

  1. Unit 1: Finite State Machines

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

    Examined in the 70-mark end-semester paper

  2. Unit 2: Regular Sets and Regular Grammars

    Regular sets and regular expressions, identity rules and manipulation of regular expressions; equivalence of RE and FA and their inter-conversion; the pumping lemma and closure properties of regular sets; the Chomsky hierarchy; right- 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
    • Chomsky hierarchy
    • Regular grammars and finite automata
  3. Unit 3: Context-Free Grammars and Pushdown Automata

    Context-free grammars and derivation trees, Chomsky and Greibach normal forms; pushdown automata and acceptance of CFLs, equivalence of CFLs and PDAs and their inter-conversion; closure properties and the pumping lemma for CFLs; an introduction to DCFLs and DPDAs.

    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
    • Pumping lemma for context-free languages
  4. Unit 4: Turing Machines

    The Turing machine model and the design of TMs, the universal Turing machine, computable functions, recursively enumerable languages and types of TMs; linear bounded automata and context-sensitive languages; counter machines.

    Examined in the 70-mark end-semester paper

    • Turing machines and their design
    • Variants of Turing machines and the universal TM
    • Recursive and recursively enumerable languages
    • Linear bounded automata and context-sensitive languages
  5. Unit 5: Decidability and Recursive Functions

    Decidable and undecidable problems, properties of recursive and recursively enumerable languages, the halting problem, Post's correspondence problem, the Ackermann function and Church's hypothesis; basic and primitive recursive functions, bounded and unbounded minimalisation, μ-recursive functions and their equivalence with Turing-computable functions.

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