Grammars, Languages generated, Chomskian Hierarchy, CFG, Ambiguity, Reduced grammars, Normal forms – FSA,NFSA, NFSA with € moves, Regular expressions, Equivalence of regular expression and FSA, Equivalence of type 3 grammars and FSA, Pumping lemma , Closure and decidability results , Myhill- Nerode theorem, Minimization, FSA with output, Problems – Pushdown Automata, Acceptance by final state and empty store, Equivalence to CFG , Deterministic PDA – Problems and Solutions – Turing Machines – Construction, Techniques of TM construction , TM as acceptor and i/o device , Problems . Generalized and restricted versions – Halting problems – Universal TM-recursive and recursively enumerable sets – Decidability – Rice’s Theorem , PCP – Time and Tape complexity of TM , P and NP, Cook’s theorem – NP-Complete Problems – Advanced topics , Regulated rewritin , L systems Grammar system – New Paradigms of computing , DNA computing , Membrane computing

Other Resources

Course Curriculum

GRAMMARS AND NATURAL LANGUAGE PROCESSING Details 53:26
GRAMMARS AND LANGUAGES GENERATED I Details 49:35
GRAMMARS AND LANGUAGES GENERATED II Details 49:27
AMBIGUITY IN CFG Details 57:10
SIMPLICATION OF CFG Details 56:3
REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG Details 55:11
GREIBACH NORMAL FORM FOR CFG Details 50:12
FINAL STATE AUTOMATA Details 56:5
NON-DETERMINISTIC FSA Details 53:53
NON DETERMINISTIC FSA I Details 45:15
NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES Details 45:48
EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS Details 58:35
REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA Details 1:3:50
DFSA TO REGULAR EXPRESSIONS Details 57:29
PROBLEMS AND SOLUTIONS Details 51:55
PUMPING LEMMAS FOR REGULAR SETS AND CFL Details 59:50
MYHILL-NERODE THEOREM Details 50:13
MINIMIZATION OF DFSA Details 55:17
FSA WITH OUTPUT MOORE AND MEALY MACHINES Details 51:43
PUSHDOWN AUTOMATA Details 45:43
PUSHDOWN AUTOMATA,EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE I Details 49:42
PUSHDOWN AUTOMATA CFG TO PDA II Details 50:39
PUSHDOWN AUTOMATA PDA TO CFG III Details 58:25
PROBLEMS AND SOLUTIONS Details 50:4
PROBLEMS AND SOLUTIONS – I Details 1:4:3
TURING MACHINES Details 58:41
TURING MACHINES I Details 52:53
TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION II Details 57:6
GENERALIZED VERSIONS OF TURING MACHINES Details 57:35
TURING MACHINE AS A GENERATING DEVICE III Details 1:9
RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM Details 57:22
PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY Details 59:3
RICE’S THEOREM,LINEAR BOUNDED AUTOMATA,PROPERTIES OF TM Details 54:17
POST’S CORRESPONDENCE PROBLEMS Details 50:49
POST’S CORRESPONDENCE PROBLEMS (Contd) TIME AND TAPE COMPLEXITY OT TM I Details 53:51
NP – COMPLETE PROBLEMS , COOK’S THEOREM Details 1:10:6
NP – COMPLETE PROBLEMS I Details 1:1:20
REGULATED REWRITING Details 59:59
L – SYSTEMS Details 55:5
GRAMMAR SYSTEMS Details 56:21
DNA COMPUTING Details 1:2
MEMBRANE COMPUTING Details 56:28

This course is part of NPTEL online courses, delivered by IIT Madras.

Course Reviews

N.A

ratings
  • 5 stars0
  • 4 stars0
  • 3 stars0
  • 2 stars0
  • 1 stars0

No Reviews found for this course.

About

FreeVideoLectures Provides you complete information about best courses online, Video tutorials, helps you in building a career !!

help@freevideolectures.com

Learn More About us

About Us
Privacy Policy
FAQ

FREEVIDEOLECTURES.COM ALL RIGHTS RESERVED.
top
FreeVideoLectures.com All rights reserved.

Setup Menus in Admin Panel