Breaking News
Home / education / Formal Languages and Automata Theory pdf Notes – FLAT pdf Notes

# Formal Languages and Automata Theory pdf Notes – FLAT pdf Notes

## 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 –

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