munotes®
Sign in
Home / Syllabus / B.E. (Computer Engineering) / Third Year CE / Semester 5 / Theoretical Computer Science

B.E. (Computer Engineering) Theoretical Computer Science 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.

Theoretical-Computer-Science.pdf
Semester 5 · Third Year CE · 4 credits · 125 marks

Loading syllabus...

Syllabus for Theoretical Computer Science

Semester 5 · Third Year CE · 4 credits · 125 marks

Module 1: Basic Concepts and Finite Automata

  • 1.1 Importance of TCS, Alphabets, Strings, Languages, Closure properties, Finite Automata (FA) and Finite State machine (FSM).
  • 1.2 Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA): Definitions, transition diagrams and Language recognizers, Equivalence between NFA with and without ε- transitions, NFA to DFA Conversion, Minimization of DFA, FSM with output: Moore and Mealy machines, Applications and limitations of FA.

Module 2: Regular Expressions and Languages

  • 2.1 Regular Expression (RE),Equivalence of RE and FA, Arden‘s Theorem, RE Applications
  • 2.2 Regular Language (RL), Closure properties of RLs, Decision properties of RLs, Pumping lemma for RLs.

Module 3: Grammars

  • 3.1 Grammars and Chomsky hierarchy
  • 3.2 Regular Grammar (RG), Equivalence of Left and Right linear grammar, Equivalence of RG and FA.
  • 3.3 Context Free Grammars (CFG) Definition, Sentential forms, Leftmost and Rightmost derivations, Parse tree, Ambiguity, Simplification and Applications, Normal Forms: Chomsky Normal Forms (CNF) and Greibach Normal Forms (GNF), Context Free language (CFL) - Pumping lemma, Closure properties.

Module 4: Pushdown Automata(PDA)

  • 4.1 Definition, Language of PDA,PDA as generator, decider and acceptor of CFG, Deterministic PDA , Non-Deterministic PDA, Application of PDA.

Module 5: Turing Machine (TM)

  • 5.1 Definition, Design of TM as generator, decider and acceptor, Variants of TM: Multitrack, Multitape, Universal TM, Applications, Power and Limitations of TMs.

Module 6: Undecidability

  • 6.1 Decidability and Undecidability, Recursive and Recursively Enumerable Languages, Halting Problem, Rice‘s Theorem, Post Correspondence Problem. Total

Useful Links

  • 1 John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman, “Introduction to Automata Theory, Languages and Computation”, 3rd Edition, Pearson Education, 2008. “Theory of Computation” , 3rd Edition, Cengage learning. 2013.
  • 2 Michael Sipser,
  • 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, Tata McGraw Hill Publication, 2013.
  • 2 Kavi Mahesh, “Theory of Computation: A Problem Solving Approach” , Kindle Edition, Wiley-India, 2011.
  • 1 www.jflap.org
  • 2 https://nptel.ac.in/courses/106/104/106104028/
  • 3 https://nptel.ac.in/courses/106/104/106104148/

Reproduced from the University of Mumbai syllabus for B.E. (Computer Engineering) under REV-2019 'C' Scheme, in force from the academic year 2021-22. 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!