Formal Languages and Automata Theory pdf

Formal Languages and Automata Theory pdf:

Click here to download the above pdf book

UNIT I

Preliminaries: Sets, Relations and functions, Methods of proof, Graphs, Languages: Basic Concepts.
Grammars: Definitions and classifications of grammar, Ambiguity, Simplification of CFGs, Normal forms.

UNIT II
Finite State Automata: DFSA, NFSA, Regular Expressions
Finite State Automata: Characterization, Properties and decidability: FSA Regular Grammars, Pumping lemma for regular sets, Closure Properties, Decidability theorems.
Finite State Automata with Output and Minimization: Myhill-Nerode theorem, Finite Automata with output.

UNIT III
Pushdown Automata: The Pushdown Automation, Equivalence between acceptance by empty store and acceptance by Final State, Equivalence of CFG and PDA.
CFG-Properties and Parsing: Pumping Lemma for CFL, Closure Properties for CFL, and Decidability results for CFL.

UNIT IV
Turing Machines: Turing Machine as a acceptor, Turing Machine as a computing device, Techniques for Turing Machine Construction.
Variations of Turing Machine: Generalized Versions, Restricted Turing Machines, Turing Machines as Enumerated, Equivalence between Turing Machines and Type Zero Languages.

UNIT V
Computability Theory: Chomsky hierarchy of languages, linear bounded automata and context sensitive language, LR(0) grammar, decidability of problems, Universal Turing Machine, un decidability of posts. Correspondence problem, Turing reducibility, Definition of P and NP problems, NP complete and NP hard problems.

TEXT BOOKS:
1. “Introduction to Formal Languages, Automata Theory and Computation”, Kamala
Krithivasan, Rama R, PEARSON.
2. “Introduction to Automata Theory Languages and Computation”. Hopcroft H.E. and

Ullman J. D. Pearson Education