Sr. No.

Content

Total 
Weightage 

Introduction to Finite Automata:

Introduction to Finite Automata,
Central Concepts of Automata Theory, Deterministic Finite Automata
(DFA), Nondeterministic Finite Automata (NFA), Finite Automata with
Epsilon Transition

Regular Expressions and Languages:

Regular Expressions, Finite
Automata and Regular Expressions, Applications of Regular
Expressions, Proving Languages Not to Be Regular, Closure Properties
of Regular Languages, Equivalence and Minimization of Automata –
Pumping Lemma.

Context Free Grammars and Languages Parse Trees:

Applications of
Context Free Grammars, Ambiguity in Grammars and Languages,
Eliminating Useless Symbols, Computing the Generating and Reachable
Symbols, Eliminating Epsilon Productions, Eliminating Unit
Productions, BacosNaur Form (BNF), Chomsky Normal Form (CNF).

Pushdown Automata, CFL and NCFL:

Definition of the Pushdown
Automaton (PDA), The Languages of a PDA, Equivalence of PDA’s and
CFG’s,Deterministic Pushdown Automata , The Pumping Lemma for
Context Free Languages , Closure Properties of Context Free Languages,
Pumping lemma for CFL, Intersections and Complements of CFL, NonCFL

Turing Machine (TM):

Problems That Computers Cannot Solve, The Turing Machine, Programming Techniques for Turing Machines
,Extensions to the Basic Turing Machine, Restricted Turing Machines ,
Turing Machines and Computers , Definition of Post’s Correspondence
Problem, A Language That Is Not Recursively Enumerable, An
Undecidable Problem That Is RE, Context sensitive languages and
Chomsky hierarchy, Other Undecidable Problems

Computable Functions:

Partial, total, constant functions, Primitive
Recursive Functions, Bounded Mineralization, Regular function, Recursive Functions