RTMNU TY Computer Engg syllabus

RTMNU · Third Year B.Tech Computer Engineering · NEP 2020

Theory of Computation

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

2 credits (2 lecture hours a week).

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

  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

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