munotes®
Sign in
Home / Syllabus / B.E. (Artificial Intelligence and Data Science) / SY BE AI and DS / Semester 4 / Computational Theory

B.E. (Artificial Intelligence and Data Science) Computational Theory Syllabus - Mumbai University 2026

This is the SY BE AI and DS syllabus under NEP 2020, in force from the academic year 2025-26. The third and fourth years of this degree are still taught on the earlier CBCS REV-2019 'C' Scheme, because the University has published no NEP syllabus for Semesters V to VIII of any engineering branch.

Computational Theory.pdf
Semester 4 · SY BE AI and DS · NEP 2020

Loading syllabus...

Syllabus for Computational Theory

Semester 4 · SY BE AI and DS · NEP 2020

Module 0: Prerequisite

  • Basic Mathematical Fundamentals: Sets, Logic, Relations, Functions, Discrete Structures.

Module I: Basics Concepts and Regular Languages 1 5 hours

  • Importance of TCS, Alphabets, Strings, 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).

Module II: Finite Automata 1 6 hours

  • Finite Automata (FA) & Finite State machine (FSM). Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA): Definitions, transition diagrams and Language recognizers, Equivalence between NFA with and ϵ- transitions, NFA to DFA Conversion, Minimization of DFA, FSM with 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.

Module III: Regular and Context Free Grammars 1 2 6 hours

  • Grammars and Chomsky Hierarchy Regular Grammar (RG), Equivalence of Left and Right linear grammar, Equivalence of RG and FA. 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) 5 hours

  • 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) 7 hours

  • 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 5 hours

  • 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

  • 1 John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman, Introduction to Automata Theory Language and Computation, 3rd Edition, Pearson Education, 2008.
  • 2 Michael Sipser, Theory of Computation, 3rd Edition, Cengage learning. 2013.
  • 3 Vivek Kulkarni, Theory of Computation, Illustrated Edition, Oxford University Press, (12 April 2013) India.

References Books

  • 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.

Online References

  • 1 https://www.jflap.org/
  • 2 https://nptel.ac.in/courses/106104028
  • 3 https://nptel.ac.in/courses/106104148

Reproduced from the University of Mumbai syllabus for B.E. (Artificial Intelligence and Data Science), item 6.20 (N), under NEP 2020, in force from the academic year 2025-26. Wording, module numbering and hours are as printed in that syllabus.

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 B.E. Artificial Intelligence and Data Science - First Year, Semester I and II - NEP 2020 - Item 7.7 (R-A) NEP 2020, Semesters I and II, in force from 2024-25 Read full PDF Read
PDF B.E. Artificial Intelligence and Data Science - Second Year, Semester III and IV - NEP 2020 - Item 6.20 (N) NEP 2020, Semesters III and IV, in force from 2025-26 Read full PDF Read
PDF B.E. Artificial Intelligence and Data Science - Third Year, Semester V and VI - CBCS REV-2019 C Scheme - Item 6.42 (R) CBCS REV-2019 'C' Scheme, Semesters V and VI, in force from 2022-23 Read full PDF Read
PDF B.E. Artificial Intelligence and Data Science - Fourth Year, Semester VII and VIII - CBCS REV-2019 C Scheme - Item 6.12 (N) CBCS REV-2019 'C' Scheme, Semesters VII and VIII, in force from 2023-24 Read full PDF Read
Issue
Done!