munotes®
Sign in
Home / Syllabus / B.E Artificial Intelligence and Machine Learning / Second Year AI ML / Semester 4 / Computational Theory

B.E Artificial Intelligence and Machine Learning Computational Theory Syllabus - Mumbai University

This is the Second Year AI-ML syllabus under NEP 2020, in force from the academic year 2025-26. The University still sets the earlier Choice Based papers alongside it for ATKT candidates, so check which scheme your exam form names before you revise.

Computational-Theory.pdf
Semester 4 · Second Year AI-ML · 3 credits · 100 marks

Loading syllabus...

Syllabus for Computational Theory

Semester 4 · Second Year AI-ML · 3 credits · 100 marks

Module 0

  • To acquire conceptual knowledge of grammar and languages. To understand the relation between Regular Language and Finite Automata. To understand the language hierarchy, CFG and CFL. To design a PDA equivalent to a given context-free grammar/language. To learn the principles of computation by designing a Turing Machine To infer the knowledge of undecidable and NP class problems. Upon completion of the course, the learners will be able to: Use TCS theory to design regular expressions that represent regular languages. Design, analyze, and optimize Finite Automata for language recognition. Design Regular and Context Free Grammars and learn to simplify the CFG. Design PDA for a given context-free grammar or language and enumerate its applications. Design Turing machines as generators, deciders, and acceptors for various computational tasks. Understand and utilize problem classification techniques for problem analysis. Detailed Content Basic Mathematical Fundamentals: Sets, Logic, Relations, Functions, Discrete Structures. 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). 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. 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

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

(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

  • Decidability and Undecidability, Recursive and Recursively Enumerable Language, Halting Problem, Rice’s Theorem, Post Correspondence Problem.

Computability

  • Self-learning Topics: NP Completeness of the SAT Problem, A Restricted Satisfiability Problem

1) 2) 3)

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

1) 2)

  • J. C. Martin, Introduction to Languages and the Theory of Computation, 4th Edition, Tata McGraw Hill Publication, 2013. Kavi Mahesh, Theory of Computation: A Problem-Solving Approach, Kindle Edition, Wiley-India, 2011.

References

  • 3 https://nptel.ac.in/courses/106104148

Reproduced from the University of Mumbai syllabus for B.E. (Artificial Intelligence and Machine Learning) 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.8 (R-A) B.E. (Artificial Intelligence and Machine Learning) Sem I & II (Revised, NEP 2020) NEP 2020 syllabus Read full PDF Read
PDF 6.21 (N) B.E. (Artificial Intelligence and Machine Learning) Sem III & IV (NEP 2020) NEP 2020 syllabus Read full PDF Read
PDF 6.42 (R) B.E. (Artificial Intelligence and Machine Learning) Third Year, Sem V & VI (REV-2019 'C' Scheme) REV-2019 'C' Scheme syllabus Read full PDF Read
PDF B.E. (Artificial Intelligence and Machine Learning) Fourth Year, Sem VII & VIII (REV-2019 'C' Scheme) REV-2019 'C' Scheme syllabus Read full PDF Read
Report or request
Done!