Share

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

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

## Topics with syllabus and resources

100.00 Introduction
• Alphabets, Strings and Languages
• Chomskey hierarchy and Grammars.
• Finite Automata (FA) and Finite State machine (FSM).
200.00 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.00 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.00 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.00 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.00 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.00 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.00 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.00 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.
S