# Theoretical Computer Science Semester 4 (SE Second Year) BE Computer Engineering University of Mumbai Topics and Syllabus

University of Mumbai Syllabus For Semester 4 (SE Second Year) Theoretical Computer Science: Knowing the Syllabus is very important for the students of Semester 4 (SE Second Year). Shaalaa has also provided a list of topics that every student needs to understand.

The University of Mumbai Semester 4 (SE Second Year) Theoretical Computer Science syllabus for the academic year 2022-2023 is based on the Board's guidelines. Students should read the Semester 4 (SE Second Year) Theoretical Computer Science Syllabus to learn about the subject's subjects and subtopics.

Students will discover the unit names, chapters under each unit, and subtopics under each chapter in the University of Mumbai Semester 4 (SE Second Year) Theoretical Computer Science Syllabus pdf 2022-2023. They will also receive a complete practical syllabus for Semester 4 (SE Second Year) Theoretical Computer Science in addition to this.

CBCGS [2017 - current]
CBGS [2013 - 2016]
Old [2000 - 2012]

## University of Mumbai Semester 4 (SE Second Year) Theoretical Computer Science Revised Syllabus

University of Mumbai Semester 4 (SE Second Year) Theoretical Computer Science and their Unit wise marks distribution

## Syllabus

100 Introduction
• Alphabets, Strings and Languages
• Chomskey hierarchy and Grammars.
• Finite Automata (FA) and Finite State machine (FSM).
200 Regular Grammar (RG)
• Regular Grammar and Regular Expression (RE):- Definition, Equivalence and Conversion from RE to RG and RG to RE.
• Equivalence of RG and FA, Converting RG to FA and FA to RG.
• Equivalence of RE and FA, Converting RE to FA and FA to RE.
300 Finite Automata
• Deterministic and Nondeterministic Finite Automata (DFA and NFA):- Definitions, Languages, Transitions (Diagrams, Functions and Tables).
• Eliminating epsilon-transitions from NFA.
• DFA, NFA:- Reductions and Equivalence.
• FSM with output: Moore and Mealy machines.
400 Regular Language (RL)
• Decision properties:- Emptiness, Finiteness and Membership.
• Pumping lemma for regular languages and its applications.
• Closure properties.
• Myhill-Nerode Theorem and An application: Text Search.
500 Context Free Grammars (CFG)
• Definition, Sentential forms, Leftmost and Rightmost derivations.
• Context Free languages (CFL): Parsing and Ambiguity.
• CFLs: Simplification and Applications.
• Normal Forms: CNF and GNF.
• Pumping lemma for CFLs and its applications.
• Closure properties and Kleene’s closure.
600 Pushdown Automata (PDA)
• Definition, Transitions (Diagrams, Functions and Tables), Graphical Notation and Instantaneous Descriptions.
• Language of PDA, Pushdown Stack Machine (PSM) as a machine with stack, Start and Final state of PSM.
• PDA/PSM as generator, decider and acceptor of CFG
• Deterministic PDA (DPDA) and Multi-stack DPDA
700 Turing Machine (TM)
• Definition, Transitions (Diagrams, Functions and Tables).
• Design of TM as generator, decider and acceptor.
• Variants of TM: Multitrack, Multitape and Universal TM.
• Equivalence of Single and Multi Tape TMs.
• Power and Limitations of TMs.
• Design of Single and Multi Tape TMs as a computer of simple functions: Unary, Binary (Logical and Arithmetic), String operations (Length, Concat, Match, Substring Check, etc)
800 Undecidability and Recursively Enumerable Languages
• Recursive and Recursively Enumerable Languages.
• Properties of Recursive and Recursively Enumerable Languages.
• Decidability and Undecidability, Halting Problem, Rice’s Theorem, Grebach’s Theorem, Post Correspondence Problem.
• Context Sensitivity and Linear Bound Automata.
900 Comparison of Scope of Languages and Machines
• Subset and Superset relation between FSM, PSM and TM.
• Subset and Superset relation between RL, CFL and Context Sensitive Language.