0
(
ratings
)
1
students
Created by:
Last updated:
September 25, 2023
Duration:
Unlimited Duration
FREE
This course includes:
Unlimited Duration
Badge on Completion
Certificate of completion
Unlimited Duration
Description
Theory of Automata, Formal Languages and Computation. Instructor: Prof. Kamala Krithivasan, Department of Computer Science and Engineering, IIT Madras.
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 Curriculum
-
- 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
About the instructor
5
5
Instructor Rating
6
Reviews
4637
Courses
24154
Students
OpenCoursa
We are an educational and skills marketplace to accommodate the needs of skills enhancement and free equal education across the globe to the millions. We are bringing courses and trainings every single day for our users. We welcome everyone woth all ages, all background to learn. There is so much available to learn and deliver to the people.
