## Formal Languages and Automata Theory (FLAT) by Dr G Kiran Kumar M Tech (Ph.D) This course deals with the definition of machine models, classification of machines by their power to recognize languages, hierarchical organization of problems depending on their complexity, logical limits to computational capacity and Undecidable problems. Code : FLAT Recommended For : B.Tech CSE 2nd Year 2nd Semester

#### After Learning this subject,you should be able to

• Construct finite state diagrams while solving problems of computer science.
• Find solutions to the problems using Turing machines.
• Design of new grammar and language

## Curriculum 18:17:27   units   |   6

• 5:01:32

UNIT 1
Finite Automata: Why Study Automata Theory?, Structural Representations, The Central Concepts of Automata Theory Part - 1, The Central Concepts of Automata Theory Part - 2, Automation & Acceptance of a String by a Finite Automation, Finite Automation, Transition Systems, DFA Part 1, DFA Part 2, NFA, Design of NFA, Find out DFA (or) NFA & Differences Between DFA and NFA, Equivalence of DFA and NFA Part - 1, Equivalence of DFA and NFA Part - 2, Conversion of NFA into DFA Part - 1, Conversion of NFA into DFA Part - 2, Finite Automata with E-Transition Part - 1, Finite Automata with E-Transition Part - 2, Finite Automata with E-Transition Part - 3, Conversion of NFA with E-moves to NFA without E-moves Part - 1, Conversion of NFA with E-moves to NFA without E-moves Part - 2, Conversion of NFA with E-moves to NFA without E-moves Part - 3, Conversion of NFA with E-moves to NFA without E-moves Part - 4, Conversion of NFA with E-moves to NFA without E-moves Part - 5, Minimization of Finite Automata Part - 1, Minimization of Finite Automata Part - 2, Minimization of Finite Automata Part - 3, Minimization of Finite Automata Part - 4, Minimization of Finite Automata Part - 5, Minimization of Finite Automata Part - 6, Moore Machine Part - 1, Moore Machine Part - 2, Mealy Machine Part - 1, Mealy Machine Part - 2, Conversion of One machine to another Part - 1, Conversion of One machine to another Part - 2, Conversion of One machine to another Part - 3, Applications and Limitation of Finite Automata.

• 5:12:35

UNIT 2
Regular Expressions: Regular Expressions & Regular Sets Part - 1, Regular Expressions & Regular Sets Part - 2, Regular Expressions & Regular Sets Part - 3, Regular Expressions & Regular Sets Part - 4, Formal Definition of Regular Expression, Identity Rules Part - 1, Identity Rules Part - 2, Equivalence of two Regular Expressions, Manipulations of Regular Expressions, Conversion of Finite Automata to Regular Expression Part - 1, Conversion of Finite Automata to Regular Expression Part - 2, Conversion of Finite Automata to Regular Expression Part - 3, Conversion of Finite Automata to Regular Expression Part - 4, Conversion of Regular Expression to Finite Automata Part - 1, Conversion of Regular Expression to Finite Automata Part - 2, Conversion of Regular Expression to Finite Automata Part - 3, Conversion of Regular Expression to Finite Automata Part - 4, Conversion of Regular Expression to Finite Automata Part - 5, Equivalence between Finite Automata and Regular Expressions, Simple Ways to Design Finite Automata Part - 1, Simple Ways to Design Finite Automata Part - 2, Simple Ways to Design Finite Automata Part - 3, Simple Ways to Design Finite Automata Part - 4, Pumping Lemma for Regular Language, Closure Properties Part - 1, Closure Properties Part - 2, Closure Properties Part - 3, Applications of Regular Expressions, Regular Grammar Part- 1, Regular Grammar Part- 2, Conversion of Finite Automata to Regular Grammar Part- 1, Conversion of Finite Automata to Regular Grammar Part- 2, Conversion of Regular Grammar to Finite Automata Part - 1, Conversion of Regular Grammar to Finite Automata Part - 2, Conversion of Regular Grammar to Finite Automata Part - 3, Conversion of Regular Expressions to Regular Grammars Part - 1, Conversion of Regular Expressions to Regular Grammars Part - 2

• 3:12:46

UNIT 3
Context Free Grammars: Formal Languages, Grammars, Classification of Grammars, Chomsky Hierarchy Theorem, Context Free Grammar, Leftmost and Rightmost Derivations,Parse Trees Part - 1, Leftmost and Rightmost Derivations,Parse Trees Part - 2, Ambiguous Grammars, Simplification of Context Free Grammars-Elimination of Useless Symbols Part-1, Simplification of Context Free Grammars-Elimination of Useless Symbols Part-2, Normal Forms for Context Free Grammars, Chomsky Normal Form(CNF) Part - 1, Chomsky Normal Form(CNF) Part - 2, Conversion of CFG to CNF by removing Null and Unit Productions Part - 1, Conversion of CFG to CNF by removing Null and Unit Productions Part - 2, Greibach Normal Form(GNF), Conversion of CFG to GNF Part- 1, Conversion of CFG to GNF Part- 2, Pumping Lemma, Closure Properties Part - 1, Closure Properties Part - 2, Closure Properties Part - 3, Applications of Context Free Grammars.

• 2:06:56

UNIT 4
Pushdown Automata: Pushdown Automata, Definition, Model, Graphical Notation, Instantaneous Description Language Acceptance of pushdown Automata, Design of Pushdown Automata Part - 1, Design of Pushdown Automata Part - 2, Design of Pushdown Automata Part - 3, Equivalence of Pushdown Automata, Deterministic and Non ? Deterministic Pushdown Automata, Context Free Grammars Conversion -CFG to PDA Part- 1, Context Free Grammars Conversion -CFG to PDA Part- 2, Context Free Grammars Conversion -PDA to CFG Part- 1, Context Free Grammars Conversion -PDA to CFG Part- 2, Context Free Grammars Conversion -PDA to CFG Part- 3, Two Stack Pushdown Automata,, Application of Pushdown Automata

• 2:14:38

UNIT 5
Turning Machine: Turing Machine, Definition, Model, Representation of Turing Machines, Instantaneous Descriptions, Transition Tables, Transition Diagrams, Language of a Turing Machine, Properties of Recursive and recursively Enumerable Languages, Design of Turing Machines Part - 1, Design of Turing Machines Part - 2, Design of Turing Machines Part - 3, Design of Turing Machines Part - 4, Design of Turing Machines Part - 5, Design of Turing Machines Part - 6, Design of Turing Machines Part - 7, Design of Turing Machines Part - 8, Design of Turing Machines Part - 9, Techniques for Turing Machine Construction, Types of Turing Machines, Church?s Thesis, Universal Turing Machine, Restricted Turing Machine

• 0:29:00

UNIT 6
Computability: Decidable and Un-decidable Problems, Halting Problem of Turing Machines, Post?s Correspondence Problem, Modified Post?s Correspondence Problem, Classes of P and NP, NPHard and NP-Complete Problems