Theory of Automata, Formal Languages and Computation

NPTEL and Indian Institute of Technology Madras via YouTube

Start learning Write review

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

Reviews

4.7 rating, based on 9 Class Central reviews

Start your review of Theory of Automata, Formal Languages and Computation

SUYASH SINGH (RA2311003030029)

The Automata course offers a deep and structured understanding of the theoretical foundations of computer science. It covers essential topics such as finite automata, regular expressions, context-free grammars, pushdown automata, and Turing machines…

The Automata course offers a deep and structured understanding of the theoretical foundations of computer science. It covers essential topics such as finite automata, regular expressions, context-free grammars, pushdown automata, and Turing machines. The course effectively bridges abstract theory with practical applications, helping students grasp how languages and machines form the basis of computation and compiler design. Concepts like decidability and computational complexity are presented in a clear and logical manner, promoting analytical and problem-solving skills. The lectures and assignments encourage critical thinking and mathematical rigor, making it ideal for students aiming to strengthen their foundation in theoretical computer science. While the material can be challenging, the systematic approach and illustrative examples make complex topics more approachable. Overall, the Automata course is intellectually stimulating, rewarding, and essential for anyone pursuing deeper studies in algorithms, programming languages, or artificial intelligence.
Abhay Oraon

"Overall, I had a great experience with the course. The instructor was knowledgeable and presented the material in an engaging way. The course content was relevant and covered all the necessary topics. I appreciated the interactive elements, such as quizzes and discussions, which helped reinforce my understanding of the material.

One thing I'd suggest improving is adding more real-world examples or case studies to illustrate key concepts. Additionally, some of the video lectures were a bit long, so breaking them up into shorter segments could make the content more digestible.

I would definitely recommend this course to others, and I'm looking forward to taking more courses from .
Hardik J.

This is one of the best free courses on Theory of Automata, Formal Languages, and Computation! The explanations are very clear and well-structured, especially the parts on DFA, NFA, PDA, and Turing Machines. The instructor connects theoretical ideas with real-world computer science concepts, which makes it easy to understand even for beginners. The pacing is excellent, and all examples are detailed and practical. I highly recommend this course to anyone preparing for university exams, GATE, or just wanting a deep understanding of computation theory.
SHAURYADEEP BHADAURIYA (RA2311003030226)

this was a pretty good course and the teacher really had full knowledge of concepts due to which i could easily understand what she ws teaching
Adarsh Kumar

i understand all the topic and clarity in the concepts and its helps me solve the problem very quickly and easily
Vinay Vishwakarma

Nice explained , help me learn more about the automata theory other than my syllabus. Help me to understand how Turing machine works in real life how it going to be halt
Shahil Parmar

I recently took this course, and it was an excellent choice for someone new to the subject. The lessons are well-structured, easy to follow, and paced just right—not too fast or overwhelming. The instructor explains concepts clearly and uses simple examples that make learning fun and engaging. There are also plenty of practical exercises to help reinforce what you’ve learned.

What I especially liked was the supportive community and resources available for extra help. Overall, this course is a great starting point for beginners looking to build a solid foundation.

Highly recommended if you’re just getting started!
227y1a6748 227y1a6748

Theory of automata and formal theory is best subject gain knowledge on it and improve skills on this course is seems interesting and learn many things by this course in the above classes
A.joyce

Osm course the teacher is so knowledgeable and explains clearly. This course is helpful for all the research students.its such a wonderful opportunity to access this course in free. Thank you