CBCGS [2017 - current]

CBGS [2013 - 2016]

Old [2000 - 2012]

## Topics with syllabus and resources

1 Introduction

syllabus ▼

- Alphabets, Strings and Languages
- Chomskey hierarchy and Grammars.
- Finite Automata (FA) and Finite State machine (FSM).

2 Regular Grammar (RG)

syllabus ▼

- 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.

3 Finite Automata

syllabus ▼

- 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.

4 Regular Language (RL)

syllabus ▼

- Decision properties:- Emptiness, Finiteness and Membership.
- Pumping lemma for regular languages and its applications.
- Closure properties.
- Myhill-Nerode Theorem and An application: Text Search.

5 Context Free Grammars (CFG)

syllabus ▼

- 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.

6 Pushdown Automata (PDA)

syllabus ▼

- 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

7 Turing Machine (TM)

syllabus ▼

- 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)

8 Undecidability and Recursively Enumerable Languages

syllabus ▼

- 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.

9 Comparison of Scope of Languages and Machines

syllabus ▼

- Subset and Superset relation between FSM, PSM and TM.
- Subset and Superset relation between RL, CFL and Context Sensitive Language.

#### Question PapersVIEW ALL [9]

view

Question Papers For All Subjects- Applied Mathematics 4 2007 to 2018

question paper - Analysis of Algorithm 2015 to 2018

question paper - Computer Organisation and Architecture 2009 to 2018

question paper - Database Management Systems 2007 to 2018

question paper - Theoretical Computer Science 2014 to 2018

question paper - Computer Graphics 2009 to 2018

question paper - Operating Systems 2009 to 2018

question paper - Analysis of Algorithm and Design 2007 to 2014

question paper - Analog and Digital Communication 2007 to 2014

question paper