munotes®
Sign in
Home / Syllabus / B.E. (Computer Engineering) / Second Year CE / Semester 4 / Computational Theory

B.E. (Computer Engineering) Computational Theory Syllabus - Mumbai University 2026

The University has moved this degree onto NEP 2020 one year at a time. The first and second years are NEP 2020 syllabi; the third and fourth years are still examined on the REV-2019 'C' Scheme, which is what the University sets for them this year.

Computational-Theory.pdf
Semester 4 · Second Year CE · 3 credits

Loading syllabus...

Syllabus for Computational Theory

Semester 4 · Second Year CE · 3 credits

Module 0: Prerequisite

  • Basic Mathematical Fundamentals: Sets, Logic, Relations, Functions, Discrete Structures. Importance of TCS, Alphabets, Strings, Languages

Module I: Basics Concepts and Regular Languages

  • Regular operations, Regular Expression, Arden's theorem, RE Applications, Regular Language, Closure properties. Decision properties of RLs, Pumping lemma for RLs. Self-learning Topics: RE in text search and replace, Application of Regular Languages in Compiler Design, Text Processing, and Natural Language Processing (NLP). Finite Automata (FA) & Finite State machine (FSM).

Module II: Finite Automata

  • Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA): Definitions, transition diagrams and Language recognizers, Equivalence between NFA with and ϵ- transitions, NFA output: Moore and Mealy machines, Applications and limitations of FA. Self-learning Topics: State Elimination Method for converting FA to RE, Minimization of DFA using Equivalence Theorem, Conversion of Moore to Mealy & Mealy to Moore machine. Grammars and Chomsky Hierarchy Regular Grammar (RG), Equivalence of Left and Right linear grammar, Equivalence of RG and FA.

Module III: Regular and Context Free Grammars

  • Context Free Grammars (CFG) Definition, Sentential forms, Leftmost and Rightmost derivations, Parse tree, Ambiguity, Simplification of CFG: Eliminating unit productions, useless production, useless symbols, and Є-productions, Normal Forms: Chomsky Normal Form (CNF) and Greibach Normal Form (GNF), Context Free language (CFL) Application: Parser, Markup languages; Pumping lemma, Closure properties. Self-learning Topics: Left Recursion and Its Elimination, Applications of CFGs in XML Parsing, and Natural Language Processing (NLP).

Module IV: Pushdown Automata (PDA)

  • Definition, Language of PDA, PDA as generator, decider and acceptor of CFG, Deterministic PDA , Non Deterministic PDA, Equivalence of PDA and CFG, Application of PDA. Self-learning Topics: Parsing & PDA: Top-Down Parsing, Bottom-up Parsing, Closure properties and Deterministic PDA.

Module V: Turing Machine (TM)

  • Definition, Design of TM as generator, decider and acceptor, Variants of TM: Multitrack, Multitape, Universal TM, Applications, Power and Limitations of TMs. Self-learning Topics: Algorithms using Turing Machine, The Model of Linear Bounded Automata

Module VI: Decidability and Computability

  • Decidability and Undecidability, Recursive and Recursively Enumerable Language, Halting Problem, Rice’s Theorem, Post Correspondence Problem. Self-learning Topics: NP Completeness of the SAT Problem, A Restricted Satisfiability Problem

Text Books

  • 3 Vivek Kulkarni, Theory of Computation, Illustrated Edition, Oxford University Press, (12 April 2013) India.
  • 1 J. C. Martin, Introduction to Languages and the Theory of Computation, 4th Edition, References Tata McGraw Hill Publication, 2013.
  • 2 Kavi Mahesh, Theory of Computation: A Problem-Solving Approach, Kindle Edition, Wiley-India, 2011.
  • 1 https://www.jflap.org/ Online 2) https://nptel.ac.in/courses/106104028
  • 3 https://nptel.ac.in/courses/106104148

Reproduced from the University of Mumbai syllabus for B.E. (Computer Engineering) under NEP 2020, in force from the academic year 2025-26. Wording is as printed in that syllabus. Module numbering is as printed there too.

The complete syllabus

This subject is cut from the University circular for its year. Open a document here if you want the whole thing rather than a single subject.

PDF 7.9 (R-A) B.E. (Computer Engineering) Sem I & II (Revised, NEP 2020) NEP 2020 syllabus Read full PDF Read
PDF 6.24 (N) B.E. (Computer Engineering) Sem III & IV (NEP 2020) NEP 2020 syllabus Read full PDF Read
PDF 6.15 B.E. (Computer Engineering) Third Year, Sem V & VI (REV-2019 'C' Scheme) REV-2019 'C' Scheme syllabus Read full PDF Read
PDF 6.41 (R) B.E. (Computer Engineering) Fourth Year, Sem VII & VIII (REV-2019 'C' Scheme) REV-2019 'C' Scheme syllabus Read full PDF Read
Report or request
Done!