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.