Module – I

Introduction to Automata: The Methods Introduction to Finite Automata, Structural Representations, Automata and Complexity.

Proving Equivalences about Sets, The Contrapositive, Proof by Contradiction,

Inductive Proofs: General Concepts of Automata Theory: Alphabets Strings, Languages, Applications of Automata Theory.

Module – II

Finite Automata: The Ground Rules, The Protocol, Deterministic Finite Automata: Definition

of a Deterministic Finite Automata, How a DFA Processes Strings, Simpler Notations for

DFA’s, Extending the Transition Function to Strings, The Language of a DFA

Nondeterministic Finite Automata: An Informal View. The Extended Transition Function, The

Languages of an NFA, Equivalence of Deterministic and Nondeterministic Finite Automata.

Finite Automata With Epsilon-Transitions: Uses of Î-Transitions, The Formal Notation for an

Î-NFA, Epsilon-Closures, Extended Transitions and Languages for Î-NFA’s, Eliminating Î-

Transitions.

Module – III

Regular Expressions and Languages: Regular Expressions: The Operators of regular Expressions, Building Regular Expressions, Precedence of Regular-Expression Operators, Precedence of Regular-Expression Operators

Finite Automata and Regular Expressions: From DFA’s to Regular Expressions, Converting

DFA’s to Regular Expressions, Converting DFA’s to R egular Expressions by Eliminating States,

Converting Regular Expressions to Automata.

Algebraic Laws for Regular Expressions:

Properties of Regular Languages: The Pumping Lemma for Regular Languages, Applications of the Pumping Lemma Closure Properties of Regular Languages, Decision Properties of Regular Languages, Equivalence and Minimization of Automata,

Module – IV

Context-Free Grammars and Languages: Definition of Context-Free Grammars, Derivations Using a Grammars Leftmost and Rightmost Derivations, The Languages of a Grammar,

Parse Trees: Constructing Parse Trees, The Yield of a Parse Tree, Inference Derivations, and Parse Trees, From Inferences to Trees, From Trees to Derivations, From Derivation to Recursive Inferences,