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 2021-2022 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 2021-2022. They will also receive a complete practical syllabus for Semester 4 (SE Second Year) Theoretical Computer Science in addition to this.
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
University of Mumbai Semester 4 (SE Second Year) Theoretical Computer Science Course Structure 2021-2022 With Marking Scheme
| # | Unit/Topic | Marks |
|---|---|---|
| 100 | Introduction | |
| 200 | Regular Grammar (RG) | |
| 300 | Finite Automata | |
| 400 | Regular Language (RL) | |
| 500 | Context Free Grammars (CFG) | |
| 600 | Pushdown Automata (PDA) | |
| 700 | Turing Machine (TM) | |
| 800 | Undecidability and Recursively Enumerable Languages | |
| 900 | Comparison of Scope of Languages and Machines | |
| Total | - |
Syllabus
- Alphabets, Strings and Languages
- Chomskey hierarchy and Grammars.
- Finite Automata (FA) and Finite State machine (FSM).
- 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.
- 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.
- Decision properties:- Emptiness, Finiteness and Membership.
- Pumping lemma for regular languages and its applications.
- Closure properties.
- Myhill-Nerode Theorem and An application: Text Search.
- 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.
- 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
- 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)
- 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.
- Subset and Superset relation between FSM, PSM and TM.
- Subset and Superset relation between RL, CFL and Context Sensitive Language.
