Share
Notifications

View all notifications

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

Login
Create free account


      Forgot password?
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
View in app×