Overview
 Units 6
 Duration 18:17:27
 Branch CSE
 Language English
Course Description
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.
Recommended For
B.E/B.Tech Computer Science and Engineering
University
Learning Outcomes
 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


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 ETransition Part  1, Finite Automata with ETransition Part  2, Finite Automata with ETransition Part  3, Conversion of NFA with Emoves to NFA without Emoves Part  1, Conversion of NFA with Emoves to NFA without Emoves Part  2, Conversion of NFA with Emoves to NFA without Emoves Part  3, Conversion of NFA with Emoves to NFA without Emoves Part  4, Conversion of NFA with Emoves to NFA without Emoves 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:01:32



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  25:12:35



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 GrammarsElimination of Useless Symbols Part1, Simplification of Context Free GrammarsElimination of Useless Symbols Part2, 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.3:12:46



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 Automata2:06:56



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 Machine2:14:38



UNIT 6 Computability: Decidable and Undecidable Problems, Halting Problem of Turing Machines, Post?s Correspondence Problem, Modified Post?s Correspondence Problem, Classes of P and NP, NPHard and NPComplete Problems0:29:00

Instructor
Dr G Kiran Kumar M Tech (Ph.D)
A senior professor with 18+ years of experience in teaching engineering subjects for students from the Computer Science and Engineering stream. He is currently working at a reputed college in Hyderabad. His area of specialization has been data mining and spatial data mining. A favourite to the student community, Dr. Kiran delivers lectures in a way that is easy to understand. To his credit, he has more than 20 journals and papers published at the national and international levels.