RTMNU TY IT syllabus

RTMNU · Third Year B.Tech Information Technology · NEP 2020

Theory of Computation

BIT5T17 · Semester V · 2 credits · College 30 + university 70

The scheme gives it 2 credits (2 lecture hours a week); its course page lists 3 lecture hours.

All notes for this subject
  1. Unit 1: Introduction

    7 hours

    Strings, alphabets, languages and their operations; finite-state machines and the finite-automaton model, acceptance of strings and languages; NFA, DFA, their equivalence and NFA-to-DFA conversion; minimisation of FSMs and equivalence of two 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 regular expressions, their identities and manipulation; equivalence of RE and FA and their inter-conversion; the pumping lemma and closure properties of regular sets; regular, right- and left-linear grammars, their equivalence with FA and 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 and derivation trees; Chomsky and Greibach normal forms; pushdown automata — definition, model and acceptance of CFLs; equivalence of CFLs and PDAs and their inter-conversion; properties of CFLs.

    Examined in the 70-mark end-semester paper

  4. Unit 4: Turing Machine

    7 hours

    Turing machines — definition, model and design; the universal Turing machine and computable functions; recursively enumerable languages; Church's hypothesis; counter machines and types of TM; undecidability, the properties of recursive and recursively enumerable languages, the Post 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

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