**Formal Languages & Automata Theory pdf Notes – FLAT pdf Notes file**

Formal Languages & Automata Theory pdf Notes – FLAT notes pdf – FLAT pdf Notes file to download are listed below please check it –

**FLAT Latest Material Links**

**Download FLAT:Complete Notes**

**Download FLAT:Unit 1 Notes**

**Download FLAT:Unit 2 Notes**

**Download FLAT:Unit 3 Notes**

**Download FLAT:Unit 4 Notes**

**Download FLAT:Unit 5 Notes**

**FLAT Old Material Links**

**Download FLAT:Complete Notes**

**Download FLAT:Chapter 1 Notes**

**Download FLAT:Chapter 2 Notes**

**Download FLAT:Chapter 3 Notes**

**Download FLAT:Chapter 4 Notes**

**Download FLAT:Chapter 5 Notes**

**Note :-** These notes are according to the R09 Syllabus book of JNTU.In R13 and R15,8-units of R09 syllabus are combined into 5-units in R13 and R15 syllabus. If you have any doubts please refer to the JNTU Syllabus Book.

**UNIT I**

- Fundamentals : Strings, Alphabet, Language, Operations, Finite state machine, definitions, finite automaton model, acceptance of strings, and languages,
- deterministic finite automaton and non deterministic finite automaton, transition diagrams and Language recognizers.

**UNIT II**

- Finite Automata : NFA with Î transitions – Significance, acceptance of languages. Conversions and Equivalence : Equivalence between NFA with and without Î transitions,
- NFA to DFA conversion, minimisation of FSM, equivalence between two FSM’s, Finite Automata with output- Moore and Melay machines.

**UNIT III**

- Regular Languages : Regular sets, regular expressions, identity rules, Constructing finite Automata for a given regular expressions, Conversion of Finite Automata to Regular expressions.
- Pumping lemma of regular sets, closure properties of regular sets (proofs not required).

**UNIT IV**

- Grammar Formalism : Regular grammars-right linear and left linear grammars, equivalence between regular linear grammar and FA, inter conversion,
- Context free grammar, derivation trees, sentential forms. Right most and leftmost derivation of strings.

**UNIT V**

- Context Free Grammars : Ambiguity in context free grammars. Minimisation of Context Free Grammars. Chomsky normal form,
- Greiback normal form, Pumping Lemma for Context Free Languages. Enumeration of properties of CFL (proofs omitted).

**UNIT VI**

- Push Down Automata : Push down automata, definition, model, acceptance of CFL, Acceptance by final state and acceptance by empty state and its equivalence.
- Equivalence of CFL and PDA, interconversion. (Proofs not required). Introduction to DCFL and DPDA.

**UNIT VII**

- Turing Machine : Turing Machine, definition, model, design of TM, Computable functions, recursively enumerable languages.
- Church’s hypothesis, counter machine, types of Turing machines (proofs not required).

**UNIT VIII**

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

**Text books –** Formal Languages & Automata Theory Notes – FLAT notes pdf – FLAT pdf notes – FLAT Pdf – FLAT Notes

1. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.

2. Introduction to languages and the Theory of Computation ,John C Martin, TMH

3. “Elements of Theory of Computation”, Lewis H.P. & Papadimition C.H. Pearson /PHI.

4 Theory of Computer Science – Automata languages and computation -Mishra and Chandrashekaran, 2nd edition, PHI