Learn · NPTEL

Course11110301641 lectures

Formal Languages and Automata Theory

Dr. K.V. Krishna and Dr. Diganta Goswami · IIT Guwahati

Start with lecture 1 At NPTEL

Lectures

Languages and Finite Representation

  1. Introduction Video
  2. Alphabet, Strings, Languages Video
  3. Finite Representation Video

Grammars

  1. Grammars (CFG) Video
  2. Derivation Trees Video
  3. Regular Grammars Video

Finite Automata

  1. Finite Automata Video
  2. Nondeterministic Finite Automata Video
  3. NFA DFA Video

Minimization of Finite Automata

  1. Myhill-Nerode Theorem Video
  2. Minimization Video

RL ? RG ? FA

  1. RE => FA Video
  2. FA => RE Video
  3. FA RG Video

Variants of Finite Automata

  1. Variants of FA Video

Properties of Regular Languages

  1. Closure Properties of RL Video
  2. Homomorphism Video
  3. Pumping Lemma Video

Simplification of CFGs

  1. Simplification of CFG Video
  2. Normal Forms of CFG Video

Properties of CFLs

  1. Properties of CFLs Video

Pushdown Automata

  1. Pushdown Automata Video
  2. PDA CFG Video

Turing Machines

  1. Turing Machines Video
  2. Turing Computable Functions Video
  3. Combining Turing Machines Video
  4. Multi Input Video
  5. Turing Decidable Languages Video
  6. Varients of Turing Machines Video

Structured Grammars

  1. Structured Grammars Video

Decidability and Undecidability

  1. Decidability Video
  2. Undecidability1 Video
  3. Undecidability2 Video
  4. Undecidability3 Video

Introduction to Complexity Theory

  1. Time Bounded Turing Machines Video
  2. P and NP Video
  3. NP-Completeness Video
  4. NP-Complete Problems1 Video
  5. NP-Complete Problems2 Video
  6. NP-Complete Problems3 Video

Chomsky Hierarchy

  1. Chomsky Hierarchy Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Guwahati
Department
Mathematics
Taught by
Dr. K.V. Krishna, Dr. Diganta Goswami
Level
Undergraduate
Language
English
Subjects
Mathematics
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed