BAMU TY Computer syllabus

BAMU · Third Year B.E./B.Tech Computer Science and Engineering · NEP 2020

Theory of Computation

PCCT-4 · Semester V · 3 credits · CIA 40 + SEE 60

All notes for this subject
  1. Module 1: Finite Automata and Formal Languages; Regular Expressions and Regular Languages

    15 hours

    DFA, NFA and NFA with ε-moves, NFA-to-DFA conversion, equivalence and minimisation of DFA, finite automata with output; regular expressions and their algebraic laws, equivalence with finite automata, Arden's theorem, the pumping lemma and closure properties of regular languages.

    Examined in the 60-mark end-semester paper

  2. Module 2: Context-Free Grammars and Languages; Pushdown Automata

    15 hours

    CFGs, derivations, parse trees and ambiguity, simplification, CNF and GNF; PDAs and their acceptance, equivalence of PDA and CFG, deterministic and non-deterministic PDAs, the pumping lemma for CFLs and linear bounded automata.

    Examined in the 60-mark end-semester paper

  3. Module 3: Turing Machines and Computability; Decidability and Computational Complexity

    15 hours

    Turing machines and their design, random-access and non-deterministic TMs, the universal TM, the Church–Turing hypothesis and the halting problem; decidable and undecidable problems, recursive and recursively enumerable languages, PCP, P, NP, NP-complete and NP-hard problems.

    Examined in the 60-mark end-semester paper

Module contents are summarised from the official BAMU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Marathwada University (BAMU).