Theory of Automata, Formal Languages and Computation

Overview Grammars, Languages generated, Chomskian Hierarchy, CFG, Ambiguity, Reduced grammars, Normal forms - FSA,NFSA, NFSA with moves

Beginner 0(0 Ratings) 0 Students enrolled English
Created by skill expert
Last updated Sat, 18-Jun-2022
+ 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
+ View more
Other related courses
34:30:27 Hours
Updated Wed, 08-Jun-2022
0 0 Free
27:10:39 Hours
0 0 Free
20:48:51 Hours
Updated Wed, 08-Jun-2022
0 0 Free
07:24:45 Hours
0 0 Free
39:26:26 Hours
0 0 Free
About instructor

skill expert

0 Reviews | 17 Students | 467 Courses
Student feedback
0
0 Reviews
  • (0)
  • (0)
  • (0)
  • (0)
  • (0)

Reviews

Free
Includes: