YoVDO

Theory of Automata, Formal Languages and Computation

Offered By: NPTEL via YouTube

Tags

Automata Theory Courses Regular Expressions Courses Turing Machines Courses NP-Complete Problems Courses Formal Languages Courses

Course Description

Overview

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 like grammars, context-free grammars, finite state automata, and regular expressions, pushdown automata, Turing machines, decidability, complexity theory, DNA computing, membrane computing.


Syllabus

Mod-01 Lec-01 GRAMMARS AND NATURAL LANGUAGE PROCESSING.
Mod-01 Lec-02 GRAMMARS AND LANGUAGES GENERATED.
Mod-01 Lec-03 GRAMMARS AND LANGUAGES GENERATED (Contd).
Mod-01 Lec-04 AMBIGUITY IN CFG.
Mod-01 Lec-05 SIMPLICATION OF CFG.
Mod-01 Lec-06 REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG.
Mod-01 Lec-07 GREIBACH NORMAL FORM FOR CFG.
Mod-02 Lec-08 FINAL STATE AUTOMATA.
Mod-02 Lec-09 NON-DETERMINISTIC FSA.
Mod-02 Lec-10 NON DETERMINISTIC FSA (Contd).
Mod-02 Lec-11 NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES.
Mod-02 Lec-12 EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS.
Mod-02 Lec-13 REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA.
Mod-02 Lec-14 DFSA TO REGULAR EXPRESSIONS.
Mod-02 Lec-15 PROBLEMS AND SOLUTIONS.
Mod-02 Lec-16 PUMPING LEMMAS FOR REGULAR SETS AND CFL.
Mod-02 Lec-17 MYHILL-NERODE THEOREM.
Mod-02 Lec-18 MINIMIZATION OF DFSA.
Mod-02 Lec-19 FSA WITH OUTPUT MOORE AND MEALY MACHINES.
Mod-03 Lec-20 PUSHDOWN AUTOMATA.
Mod-03 Lec-21 PUSHDOWN AUTOMATA,EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE.
Mod-03 Lec-22 PUSHDOWN AUTOMATA CFG TO PDA.
Mod-04 Lec-23 PUSHDOWN AUTOMATA PDA TO CFG.
Mod-04 Lec-24 PROBLEMS AND SOLUTIONS-I.
Mod-04 Lec-25 PROBLEMS AND SOLUTIONS - III.
Mod-05 Lec-26 TURING MACHINES.
Mod-05 Lec-27 TURING MACHINES (Contd).
Mod-05 Lec-28 TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION.
Mod-05 Lec-29 GENERALIZED VERSIONS OF TURING MACHINES.
Mod-05 Lec-30 TURING MACHINE AS A GENERATING DEVICE.
Mod-06 Lec-31 RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM.
Mod-06 Lec-32 PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY.
Mod-06 Lec-33 RICE'S THEOREM,LINEAR BOUNDED AUTOMATA,PROPERTIES OF TM.
Mod-06 Lec-34 POST'S CORRESPONDENCE PROBLEMS.
Mod-07 Lec-35 POST'S CORRESPONDENCE PROBLEMS (Contd) TIME AND TAPE COMPLEXITY OT TM.
Mod-07 Lec-36 NP - COMPLETE PROBLEMS , COOK'S THEOREM.
Mod-07 Lec-37 NP - COMPLETE PROBLEMS (Contd).
Mod-08 Lec-38 REGULATED REWRITING.
Mod-08 Lec-39 L - SYSTEMS.
Mod-08 Lec-40 GRAMMAR SYSTEMS.
Mod-09 Lec-41 DNA COMPUTING.
Mod-09 Lec-42 MEMBRANE COMPUTING.


Taught by

nptelhrd

Tags

Related Courses

Automata Theory
Stanford University via edX
Theory of Computation
Massachusetts Institute of Technology via MIT OpenCourseWare
Alan Turing's Wonderful Machine
Pluralsight
Formal Language and Automata Theory- An Application in Compiler Design
Chhattisgarh Swami Vivekanand Technical University via Swayam
Formal Language and Automata Theory- An Application in Compiler Design (औपचारिक भाषा और स्वचालित सिद्धांत: कंपाइलर डिज़ाइन में एक अनुप्रयोग)
IGNOU via Swayam