B.Sc. (Computer Science) Theory of Computation Syllabus - Mumbai University
This is the SY BSc Computer Science syllabus under NEP 2020, in force from the academic year 2025-26. The University still sets the earlier Choice Based papers alongside it — her Summer 2026 third-year timetables name that scheme — so check which scheme your exam form names before you revise.
Loading syllabus...
Syllabus for Theory of Computation
Module I
- Introduction to Theory of Computation: Basics of Computation, Importance of Theory of Computation in Computer Science, Mathematical Foundations (Sets, Relations, Functions, Proof Techniques)
- Automata Theory: Defining Automaton, Finite Automaton, Transitions and Its properties, Acceptability by Finite Automaton, Nondeterministic Finite State Machines, DFA and NDFA equivalence, Mealy and Moore Machines, Minimizing Automata.
- Formal Languages: Defining Grammar, Derivations, Languges generated by Grammar, Chomsky Classification of Grammar and Languages, Recursive Enumerable Sets, Operations on Languages, Languages and Automata
- Regular Languages: Regular Grammar, Regular Expressions, Finite automata and Regular Expressions, Pumping Lemma and its Applications, Closure Properties, Regular Sets and Regular Grammar Context Free Languages: Context-free Languages, Derivation Tree, Ambiguity of Grammar, CFG simplification, Normal Forms, Pumping Lemma for CFG
Module II
- Pushdown Automata: Definitions, Acceptance by PDA, PDA and CFG
- Linear Bound Automata: The Linear Bound Automata Model, Linear Bound Automata and Languages.
- Turing Machines: Turing Machine Definition, Representations, Acceptability by Turing Machines, Designing and Description of Turing Machines, Turing Machine Construction, Variants of Turing Machine, Decidability and Undecidability, The Church-Turing thesis, Universal Turing Machine, Halting Problem, Introduction to Unsolvable Problems
- Computability and Complexity: Time Complexity and Space Complexity, Big-O Notation, Class P and Class NP, NP-Complete and NP-Hard Problems, Polynomial Reductions, Introduction to Complexity Hierarchies
Text Books
- 1 Theory of Computer Science, K. L. P Mishra, Chandrasekharan, PHI,3rd Edition
- 2 Introduction to Computer Theory, Daniel Cohen, Wiley,2nd Edition
- 3 Introductory Theory of Computer Science, E.V. Krishnamurthy,Affiliated East- West Press.
- 1 Theory of Computation, Kavi Mahesh, Wiley India
- 2 Elements of The Theory of Computation, Lewis, Papadimitriou, PHI
- 3 Introduction to Languages and the Theory of Computation, John E Martin, McGraw-Hill Education
- 4 Introduction to Theory of Computation, Michel Sipser, Thomson
Reproduced from the University of Mumbai syllabus for B.Sc. (Computer Science) 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.