1
Theory of Automata, Formal Languages and Computation. Instructor: Prof. Kamala Krithivasan, Department of Computer Science and Engineering, IIT Madras.
FREE
This course includes
Hours of videos
1166 years, 6 months
Units & Quizzes
42
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
This course provides an introduction to the basic models of computability, covering topics: grammars, context free grammars, finite state automata and regular expressions, pushdown automata, Turing machines, decidability, complexity theory, DNA computing, membrane computing. (from nptel.ac.in)
Course Currilcum
-
- Lecture 01 – Grammars and Natural Language Processing Unlimited
- Lecture 02 – Grammars and Languages Generated Unlimited
- Lecture 03 – Grammars and Languages Generated (cont.) Unlimited
- Lecture 04 – Ambiguity in CFG (Context Free Grammar) Unlimited
- Lecture 05 – Simplification of CFG Unlimited
- Lecture 06 – Removal of Unit Productions, Chomsky Normal Form for CFG Unlimited
- Lecture 07 – Greibach Normal Form for CFG Unlimited
-
- Lecture 08 – Finite State Automata Unlimited
- Lecture 09 – Nondeterministic Finite State Automata Unlimited
- Lecture 10 – Nondeterministic Finite State Automata (cont.) Unlimited
- Lecture 11 – Nondeterministic Finite State Automata with Epsilon-Moves Unlimited
- Lecture 12 – Equivalence between FSA and Type 3 Grammars Unlimited
- Lecture 13 – Regular Expressions, Regular Expressions to NFSA Unlimited
- Lecture 14 – DFSA to Regular Expressions Unlimited
- Lecture 15 – Problems and Solutions I Unlimited
- Lecture 16 – Pumping Lemmas for Regular Sets and CFL Unlimited
- Lecture 17 – Myhill-Nerode Theorem Unlimited
- Lecture 18 – Minimization of DFSA Unlimited
- Lecture 19 – FSA with Output Moore and Mealy Machines Unlimited
- Lecture 20 – Pushdown Automata Unlimited
- Lecture 21 – Pushdown Automata, Equivalence between Acceptance by Empty Store and … Unlimited
- Lecture 22 – Pushdown Automata CFG to PDA Unlimited
- Lecture 23 – Pushdown Automata PDA to CFG Unlimited
- Lecture 26 – Turing Machines Unlimited
- Lecture 27 – Turing Machines (cont.) Unlimited
- Lecture 28 – Turing Machines as Acceptor, Techniques for Turing Machine Construction Unlimited
- Lecture 29 – Generalized Versions of Turing Machines Unlimited
- Lecture 30 – Turing Machine as a Generating Device Unlimited
- Lecture 35 – Post’s Correspondence Problems (cont.), Time and Tape Complexity of TM Unlimited
- Lecture 36 – NP-Complete Problems, Cook’s Theorem Unlimited
- Lecture 37 – NP-Complete Problems (cont.) Unlimited
- Lecture 41 – DNA Computing Unlimited
- Lecture 42 – Membrane Computing Unlimited
