Mumbai University SE Computer syllabus

Mumbai University · Second Year Computer Engineering · NEP 2020

Computational Theory

2114111 · Semester IV · 3 credits · Internal tests 40 + end-semester 60

End-semester paper (2 hours): Six questions of 20 marks; Q1 is compulsory and you answer three.

All notes for this subject
  1. Module 1: Basic Concepts and Regular Languages

    5 hours

    Alphabets, strings and languages; regular operations and expressions; Arden's theorem; closure and decision properties; the pumping lemma for regular languages.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  2. Module 2: Finite Automata

    6 hours

    DFA and NFA as recognisers; ε-transitions; NFA to DFA; DFA minimisation; Moore and Mealy machines; applications and limits of FA.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  3. Module 3: Regular and Context-free Grammars

    9 hours

    Grammars and the Chomsky hierarchy; regular grammars, left and right linear grammars and their equivalence with FA; CFGs, derivations, parse trees and ambiguity; simplification; CNF and GNF; the pumping lemma and closure of CFLs.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  4. Module 4: Pushdown Automata

    5 hours

    PDA as generator, decider and acceptor; deterministic and nondeterministic PDA; equivalence of PDA and CFG; applications.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  5. Module 5: Turing Machines

    7 hours

    Designing TMs as generators, deciders and acceptors; multitrack and multitape TMs; the universal TM; power and limits of TMs.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  6. Module 6: Decidability and Computability

    5 hours

    Decidable and undecidable problems; recursive and recursively enumerable languages; the halting problem; Rice's theorem; the Post correspondence problem.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

Module contents are summarised from the official Mumbai University syllabus . AiCanCode.org is not affiliated with the University of Mumbai.