Theory of Automata, Formal Languages and Computation

+ View more

Course overview

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 - Rices Theorem , PCP - Time and Tape complexity of TM , P and NP, Cooks theorem - NP-Complete Problems - Advanced topics , Regulated rewritin , L systems Grammar system - New Paradigms of computing , DNA computing , Membrane computing

Curriculum for this course

42 Lessons 38:42:21 Hours

Lecture

42 Lessons 38:42:21 Hours

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