0

(

ratings

)

1

students

Created by:

Profile Photo

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 24 – Problems and Solutions II Unlimited
    • Lecture 25 – Problems and Solutions III 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 31 – Recursive Sets, Recursively Innumerable Sets, Encoding of TM, Halting Problem Unlimited
    • Lecture 32 – Problems and Instances, Universal TM, Decidability Unlimited
    • Lecture 33 – Rice’s Theorem, Linear Bounded Automata, Problems of TM Unlimited
    • Lecture 34 – Post’s Correspondence Problems 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 38 – Regulated Rewriting Unlimited
    • Lecture 39 – L-Systems Unlimited
    • Lecture 40 – Grammar Systems Unlimited
    • Lecture 41 – DNA Computing Unlimited
    • Lecture 42 – Membrane Computing Unlimited

About the instructor

5 5

Instructor Rating

6

Reviews

4637

Courses

24151

Students

Profile Photo
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.