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

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
Report or request
Done!