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
FLAT Old Material Links
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.
- 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.
- 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.
- 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).
- 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.
- 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).
- 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.
- 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).
- 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