UNIT 1...........................................................................1
MATHEMATICAL PRELIMINARIES
1.1 Symbol, Alphabet, String, Formal Language, Operation on languages
1.2 Sets, Relations
1.2.1 Sets and Subsets 1.2.2 Relations 1.2.3 Closure of Relations
1.3 Principal of Induction
Method of Proof by Induction

UNIT 2..............................................................................14
FINITE AUTOMATA AND REGULAR EXPRESSION
2.1 Definition of Automata, Representations of Automata, Transition Systems, Transition Functions.
2.2 Deterministic Finite Automata (DFA), Nondeterministic Finite Automata (NFA), The Equivalence of DFA and NFA
2.3 Minimization of DFA, Finite Automata with ε-Moves.
2.4 Melay and Moore Machines: Definition and Examples.
2.5 Applications of Finite Automata.
2.6 Regular Expressions.

UNIT 3............................................................................76
CONTEXT FREE GRAMMAR
3.1 Grammer: Types of Grammer.
3.2 Derivation Trees, Ambiguity in CFG.
3.3 Simplification of Context free Grammers.
3.3.1 Useless Symbols. 3.3.2 Null Production. 3.3.3 Unit Production.
3.4 Normal Forms for CFG
3.4.1Chomsky Normal Form(CNF) 3.4.2Greibach Normal Form(GNF)

UNIT 4.....................................................................................94
PUSHDOWN AUTOMATA AND TURING MACHINE
4.1 Definitions PDA, Types of PDA, Acceptance by Pushdown Automata
4.2 PDA and Context Free Language
4.3 Introduction: Turing Machine, Turing Machine Model
4.4 Representation of Turing Machine

REFERENCES.................................................................109