CBCGS [2017 - current]
CBGS [2013 - 2016]
Old [2000 - 2012]
Topics with syllabus and resources
- 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.
Question Papers For All Subjects
- Applied Mathematics 4 2007 to 2018
- Analysis of Algorithm 2015 to 2018
- Computer Organisation and Architecture 2009 to 2018
- Database Management Systems 2007 to 2018
- Theoretical Computer Science 2014 to 2018
- Computer Graphics 2009 to 2018
- Operating Systems 2009 to 2018
- Analysis of Algorithm and Design 2007 to 2014
- Analog and Digital Communication 2007 to 2014