Sr. No.

Content

Total 
Weightage 

Review of Mathematical Theory:

Sets, Functions, Logical statements, Proofs, Relations, Languages, Principal of
Mathematical Induction, Strong Principle, Recursive Definitions, Structural
Induction.

Regular Languages and Finite Automata:

Regular Expressions, Regular Languages, Application of Finite Automata,
Automata with output – Moore machine & Mealy machine, Finite Automata,
Memory requirement in a recognizer, Definitions, union- intersection and
complement of regular languages, Non Deterministic Finite Automata, Conversion
from NFA to FA,  – Non Deterministic Finite Automata, Conversion of NFA- 
to NFA, Kleene’s Theorem, Minimization of Finite automata, Regular And Non
Regular Languages – pumping lemma.

Context free grammar (CFG):

Definitions and Examples, Unions Concatenations And Kleene’s of Context free
language, Regular Grammar for Regular Language, Derivations and Ambiguity ,
Unambiguous CFG and Algebraic Expressions, BacosNaur Form (BNF), Normal
Form – CNF

Pushdown Automata, CFL And NCFL:

Definitions, Deterministic PDA, Equivalence of CFG and PDA & Conversion,
Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL.

Turing Machine (TM):

TM Definition, Model Of Computation, Turing Machine as Language Acceptor,
TM that Compute Partial Function, Church Turning Thesis, Combining TM,
Variations Of TM, Non Deterministic TM, Universal TM, Recursively and
Enumerable Languages, Context sensitive languages and Chomsky hierarchy.

Computable Functions:

Partial – Total – Constant Functions, Primitive Recursive Functions, Bounded
Mineralization, Regular function, Recursive Functions, Quantification,
Minimalization, and μ-Recursive Functions, All Computable Functions Are μRecursive

Undecidability :

A Language That Can’t Be Accepted, and a Problem That Can’t Be Decided , Non
Recursive Enumerable (RE) Language – Undecidable Problem with RE –
Undecidable Problems about TM – Undecidable Problems Involving Context-Free
Languages, Post‘s Correspondence Problem, The Class P and NP