Verify Account

UNIT-I
Finite Automata: Need of Automata Theory, Central Concepts of Automata Theory, Automation, Finite
Automation, Transition Systems, Acceptance of a String, DFA, Design of DFAs, NFA, Design of NFA,
Equivalence of DFA and NFA, Conversion of NFA into DFA, Finite Automata with Î-Transitions,
Minimization of Finite Automata, Finite Automata with Output – Mealy and Moore Machines, Applications
and Limitation of Finite Automata.
UNIT-II
Regular Expressions, Regular Sets, Identity Rules, Equivalence of two RE, Manipulations of REs, Finite
Automata and Regular Expressions, Inter Conversion, Equivalence between FA and RE, Pumping Lemma
of Regular Sets, Closure Properties of Regular Sets, Grammars, Classification of Grammars, Chomsky
Hierarchy Theorem, Right and Left Linear Regular Grammars, Equivalence between RG and FA, Inter
Conversion.
UNIT-III
Formal Languages, Context Free Grammar, Leftmost and Rightmost Derivations, Parse Trees, Ambiguous
Grammars, Simplification of Context Free Grammars – Elimination of Useless Symbols, Î-Productions
and Unit Productions, Normal Forms – Chomsky Normal Form and Greibach Normal Form, Pumping
Lemma, Closure Properties, Applications of Context Free Grammars.
Syllabus
UNIT-IV
Pushdown Automata, Definition, Model, Graphical Notation, Instantaneous Description, Language
Acceptance of Pushdown Automata, Design of Pushdown Automata, Deterministic and Non-deterministic
Pushdown Automata, Equivalence of Pushdown Automata and Context Free Grammars, Conversion,
Two Stack Pushdown Automata, Application of Pushdown Automata.
UNIT-V
Turning Machine: Definition, Model, Representation of TMs – Instantaneous Descriptions, Transition
Tables and Transition Diagrams, Language of a TM, Design of TMs, Types of TMs, Church’s Thesis,
Universal and Restricted TM, Decidable and Un-decidable Problems, Halting Problem of TMs,
Post’s Correspondence Problem, Modified PCP, Classes of P and NP, NP-Hard and NP-Complete
Problems.