Syllabus:

UNIT – I
Introduction: Basics of set theory, Relations on sets, Alphabets, Strings, Languages, Grammar formalism, Chomsky Hierarchy

Finite Automata: History of the Automata theory, Use of Automata, Characteristics of Automata, Graphical and Tabular Representation FA, Transitional system,DFA and NFA,Conversion of an NFA to DFA,NFA with є(null)Move, Equivalence of DFA and NFA,Dead state, Finite Automata with Output, Conversion of one machine to another, Minimization of Finite Automata,Myhill-Nerode Theorem, Applications of FA,Limitations of FA.

UNIT – II
Regular Languages: Regular Expressions (RE), Basics of Regular Expressions, Identities of Regular Expression,The Arden ̳s Theorem, Using Arden ̳s theorem to construct RE from FA,Equivalence of Two FAs, Equivalence of Two REs, Construction of Regular Grammar fromRE, Constructing FA from Regular Grammar,Pumping Lemma for RLs, Applications of Pumping Lemma, Closure properties of Regular Set, Decision problems of Reapplications of REs.

UNIT – III
Context Free Grammars and Languages: Definition of Context Free Grammars (CFG), Derivationsand Parse trees, Ambiguity in CFGs, Removing ambiguity, Left recursion and Left factoring, Simplification of CFGs, , Linear grammars, Normal Forms ,Closure properties for CFLs, Pumping Lemma for CFLs, Decision problems for CFLs.

UNIT – IV
Push Down Automata (PDA): Informal introduction, The Formal Definition, Graphical notation,Instantaneous description, The Languages of a PDA, Equivalence of PDAs and CFGs, Deterministic Push Down Automata.

UNIT – V
Turing Machines and Undecidability: Basics of Turing Machine (TM), Transitional Representationof TMs, Instantaneous description, Non Deterministic TM, Conversion of Regular Expression to TM, Variations of the TM, Universal TM, Linear Bounded Automata, Post Correspondence Problem(PCP), Modified PCP.

Materials for flat:

Unit-1: View/Download

Unit-2: View/Download

Unit-3: View/Download

Unit-4: View/Download

Unit-5: View/Download