Home / JNTU World / Formal Languages & Automata Theory Notes JNTU | FLAT Notes JNTU

Formal Languages & Automata Theory Notes JNTU | FLAT Notes JNTU

Formal Languages & Automata Theory Notes JNTU – FLAT Notes JNTU of Total Complete Notes

Please find the download links of Formal Languages & Automata Theory Notes JNTU | FLAT Notes JNTU are listed below:

Link:Complete Notes

Link:Chapter 1 Notes

Link:Chapter 2 Notes

Link:Chapter 3 Notes

Link:Chapter 4 Notes

Link:Chapter 5 Notes

All the above chapter are  covered according to the below units(JNTU)

FORMAL LANGUAGES AND AUTOMATA THEORY

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.

Check Also

JNTUK

JNTUK I Year Academic Calendars for B.ARCH, MCA, M.Tech and M.Pharmacy

JNTUK update for the M.Pharmacy I & II Semesters Academic Calendar For A.Y 2017-18 (2017 …

Leave a Reply

Your email address will not be published. Required fields are marked *